Merge Sort

  • Time to merge elements: (linear time)
  • Input.
    1. Step. If , DONE
    2. Step. Recursively sort and
    3. Step. MERGE the 2 sorted lists

Merge Sort Example

Session 3 - Merge Sort Tree.png#invert

Merge Sort Analysis

  • Input.
    1. Step. If , done
    2. Step. Recursively sort and
    3. Step. MERGE the 2 sorted lists

Input Time:
Step 1 Time:
Step 2 Time:
Step 3 time:

Recurrence for Merge Sort