CS205

Merge Sort

O(n log n)

Divides the array in half, recursively sorts each half, then merges them.

Merge Sort
64
34
25
12
22
11
90
0
1
2
3
4
5
6
Ready to start
Step 0 of 0
Speed:500ms
Default
Comparing
Swapping
Sorted
Pivot
Algorithm Info

Divides the array in half, recursively sorts each half, then merges them.

Best Case
O(n log n)
Average Case
O(n log n)
Worst Case
O(n log n)
Space
O(n)
How It Works
  1. Divide the array into two halves
  2. Recursively sort each half
  3. Merge the two sorted halves back together
  4. During merge: compare elements from both halves
  5. Place smaller element first, creating sorted output
  6. Base case: array of size 1 is already sorted
Pseudocode
mergeSort(arr, left, right):
    if left < right:
        mid = (left + right) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid+1, right)
        merge(arr, left, mid, right)

merge(arr, left, mid, right):
    create temp arrays L and R
    copy data to temp arrays
    merge temp arrays back into arr
Complexity Analysis
Time Complexity
Best:O(n log n)
Average:O(n log n)
Worst:O(n log n)
Space Complexity
O(n)
Stable Sort?
Yes
Advantages & Disadvantages
Advantages
  • Guaranteed O(n log n) time - always
  • Stable sort - preserves order of equal elements
  • Predictable performance regardless of input
  • Excellent for linked lists (no random access needed)
  • Parallelizable - can sort halves independently
Disadvantages
  • Requires O(n) extra space for merging
  • Not in-place - needs auxiliary arrays
  • Slightly slower than quicksort for random data
  • Overkill for small arrays
When to Use Merge Sort
  • •When stable sort is required
  • •Sorting linked lists
  • •External sorting (large files)
  • •When worst-case guarantee is important
  • •Parallel processing environments