Algorithm Guidecomplexity: O(n log n)

Merge Sort

A stable divide-and-conquer algorithm with consistent performance: split the array until indivisible, then merge back while sorting.

01Merge Sort

Explore How It Works

Starting merge sort. Split the array in half until it can't be divided further.

Split the array into two halves: 38 · 27 · 43 and 10 · 76 · 15.

Split the left half again into 38 · 27 and 43.

Split 38 · 27 into single values as well.

38 stands alone, so it is already sorted.

So is 27. Nothing left to split — time to merge.

Merge the 38 and 27 we just separated.

Compare the two fronts, 38 and 27. 27 is smaller, so it goes out first.

Put 27 down in the first slot.

One side is empty, so append the remaining 38 as is.

43, left on its own, is sorted too.

Merge 43 into the sorted 27 · 38 to complete the left half.

Compare the fronts, 27 and 43. 27 is smaller.

Put 27 down in the first slot.

Next up, 38 and 43. The left side is smaller again.

Put 38 down in the next slot.

The left side is empty, so append the remaining 43. The left half now reads 27 · 38 · 43.

Now the right half. Split it into 10 · 76 and 15.

Split 10 · 76 into single values as well.

10 can't be divided further.

Neither can 76. Time to merge the two.

Merge the 10 and 76 we just separated.

Compare the fronts, 10 and 76. 10 is smaller.

Put 10 down in the first slot.

Append the remaining 76.

15, left on its own, is sorted too.

Merge 15 into the sorted 10 · 76 to complete the right half.

Compare the fronts, 10 and 15. 10 is smaller.

Put 10 down in the first slot.

Next up, 76 and 15. This time the right side is smaller.

Put 15 down in the next slot.

Append the remaining 76. The right half now reads 10 · 15 · 76.

Merge the two sorted halves one last time. Only the fronts ever need comparing.

Compare 27 and 10. The right side is smaller.

Put 10 down in the very first slot.

Compare 27 and 15. The right side is smaller again.

Put 15 down in the next slot.

Compare 27 and 76. This time the left side is smaller.

Put 27 down in the next slot.

Compare 38 and 76. The left side is still smaller.

Put 38 down in the next slot.

Compare 43 and 76. The last value on the left is smaller.

Put 43 down in the next slot.

The left side is exhausted. Put the remaining 76 at the very end.

Merge sort is done. The order is decided as the pieces come back together, not as they are split.

Live Python

1def merge_sort(arr, low, high):

# low: 0, high: 5

2 if low < high:

3 mid = low + (high - low) // 2

4 merge_sort(arr, low, mid)

5 merge_sort(arr, mid + 1, high)

6 merge(arr, low, mid, high)

8def merge(arr, low, mid, high):

9 L = arr[low:mid+1]

10 R = arr[mid+1:high+1]

11 i = j = 0

12 k = low

13 while i < len(L) and j < len(R):

14 if L[i] <= R[j]:

15 arr[k] = L[i]

16 i += 1

17 else:

18 arr[k] = R[j]

19 j += 1

20 k += 1

21 while i < len(L):

22 arr[k] = L[i]

23 i += 1

24 k += 1

25 while j < len(R):

26 arr[k] = R[j]

27 j += 1

28 k += 1

1 / 45

02 Understand It Simply

For Everyone

🔑How It Works

Halves the input repeatedly, then merges sorted pieces by comparing their fronts. O(n log n) on any input.

💡In Plain Words

Splits the array in halves, sorts each, and merges two sorted pieces in order.

Always O(n log n) and stable.

📍Where It's Used

–Sorting that needs stability
–external sorting of large files

03 Python Implementation

A clean, readable reference implementation of the core logic of Merge Sort.

core_implementation.py

def merge_sort(arr, low, high):
    if low < high:
        mid = low + (high - low) // 2
        merge_sort(arr, low, mid)
        merge_sort(arr, mid + 1, high)
        merge(arr, low, mid, high)

def merge(arr, low, mid, high):
    L = arr[low:mid+1]
    R = arr[mid+1:high+1]
    i = j = 0
    k = low
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    while i < len(L):
        arr[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        arr[k] = R[j]
        j += 1
        k += 1