Merge Sort

sorting

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Divides the array into halves, recursively sorts them, and merges the sorted halves back together.

Time Complexity

Best

\mathrm{O}\left(n \log n\right)

Avg

\mathrm{O}\left(n \log n\right)

Worst

\mathrm{O}\left(n \log n\right)

Max Operations

Worst-case bound

n \cdot \lceil \log_2(n) \rceil

Used for efficiency calculation in Stats Panel

Space Complexity

Aux

\mathrm{O}\left(n\right)

Extra array for merging + O(log n) call stack

Pseudocode

1procedure mergeSort(A, lo, hi)

2if lo >= hi: return

3mid = (lo+hi)/2

4mergeSort(A, lo, mid)

5mergeSort(A, mid+1, hi)

6merge: compare left[i] vs right[j]

7place smaller element into A[k]

8end procedure