Editor

Python Program for Merge Sort

Intermediate · Searching and sorting

Merge sort is a divide and conquer algorithm: it splits the list in half, sorts each half the same way, and then merges the two sorted halves into one sorted list. Splitting stops at lists of one element, which are already sorted. This program prints every merge, indented by how deep the split is.

Program

merge_sort.py
def merge_sort(items, depth=0):
if len(items) <= 1:
return items # a list of 0 or 1 items is already sorted
# Divide: sort each half on its own
mid = len(items) // 2
left = merge_sort(items[:mid], depth + 1)
right = merge_sort(items[mid:], depth + 1)
# Conquer: merge the sorted halves, always taking the smaller front item
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged += left[i:] + right[j:] # leftovers are already sorted
print(" " * depth + f"Merge {left} and {right} -> {merged}")
return merged
numbers = [38, 27, 43, 3, 9, 82]
print("Original list:", numbers)
print("Sorted list:", merge_sort(numbers))
Output
Original list: [38, 27, 43, 3, 9, 82]
    Merge [27] and [43] -> [27, 43]
  Merge [38] and [27, 43] -> [27, 38, 43]
    Merge [9] and [82] -> [9, 82]
  Merge [3] and [9, 82] -> [3, 9, 82]
Merge [27, 38, 43] and [3, 9, 82] -> [3, 9, 27, 38, 43, 82]
Sorted list: [3, 9, 27, 38, 43, 82]

How it works

  1. The function splits the list at mid and calls itself on each half, until every piece has one element.
  2. The while loop merges two sorted halves by comparing their front items and taking the smaller one each time.
  3. When one half runs out, whatever is left in the other is already sorted, so it is added on the end.
  4. The deepest merges print first and with the most indentation, and the last line is the final merge of the two big halves.
  5. Merge sort always takes about n x log n steps, much faster than bubble sort on big lists, and <= keeps equal items in their original order.

Another way to write it

Bottom-up, without recursion

Bottom-up, without recursion
import heapq
numbers = [38, 27, 43, 3, 9, 82, 10]
runs = [[n] for n in numbers] # one-item lists, each already sorted
print("Start:", runs)
while len(runs) > 1:
next_runs = []
for k in range(0, len(runs), 2):
pair = runs[k:k + 2] # two neighbouring runs, or one at the end
next_runs.append(list(heapq.merge(*pair)))
runs = next_runs
print("Merged:", runs)
print("Sorted list:", runs[0])
Output
Start: [[38], [27], [43], [3], [9], [82], [10]]
Merged: [[27, 38], [3, 43], [9, 82], [10]]
Merged: [[3, 27, 38, 43], [9, 10, 82]]
Merged: [[3, 9, 10, 27, 38, 43, 82]]
Sorted list: [3, 9, 10, 27, 38, 43, 82]

Start with one-item lists and merge neighbours in pairs, round after round, until one list is left. heapq.merge() does the merging of two sorted lists.

Try it yourself

Add a counter that counts how many comparisons the merges make, and compare it with bubble sort on the same list.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises