Editor

Merge sort in Python

Merge sort splits the list in half, sorts each half the same way, then merges the two sorted halves by always taking the smaller front value. This version merges back into the original list, so you can watch the bars settle.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. merge_sort(nums, start, end) sorts the part of the list from start up to, but not including, end.
  2. A part with one value is already sorted, so the function returns at once. That is the base case.
  3. Otherwise it splits at mid and sorts the left half, then the right half, each with its own recursive call.
  4. It copies both sorted halves into left and right, then writes the smaller front value into nums[k] again and again.
  5. When one half runs out, the rest of the other half is copied in, already in order.

What to watch

  • Watch the call stack: calls go deeper until each part holds one value, and the merging happens on the way back up.
  • Watch k move right through the part being merged while its bars are rewritten in sorted order.
  • Watch i and j: they point into the copies left and right, not into nums.

The code

def merge_sort(nums, start, end):
    if end - start <= 1:
        return                       # one value is already sorted
    mid = (start + end) // 2
    merge_sort(nums, start, mid)     # sort the left half
    merge_sort(nums, mid, end)       # sort the right half
    left, right = nums[start:mid], nums[mid:end]
    i = j = 0
    k = start
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            nums[k] = left[i]
            i += 1
        else:
            nums[k] = right[j]
            j += 1
        k += 1
    for value in left[i:] + right[j:]:   # copy what is left over
        nums[k] = value
        k += 1

data = [6, 3, 8, 1, 5, 2]
merge_sort(data, 0, len(data))
print(data)
Output
[1, 2, 3, 5, 6, 8]

Open it in the editor · Python Program for Merge Sort, explained