DSA Merge Sort
Merge sort is a sorting method that splits a list into halves and merges them in order. Merging is joining two sorted lists into one sorted list.
Merging two sorted lists
A merge compares the two front values and takes the smaller one. The taken value leaves its list, so each value moves once per merge.
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1, 4, 7], [2, 3, 8]))Splitting down to singles
A base case is the smallest input that needs no more splitting. Here the base case is a list of one value, which is already sorted.
def split(values):
if len(values) <= 1:
return
mid = len(values) // 2
print(values[:mid], values[mid:])
split(values[:mid])
split(values[mid:])
split([8, 3, 7, 1])Counting merge comparisons
Only the front values are ever compared in a merge. The leftover tail of the longer list is copied with no comparisons at all.
def merge_count(left, right):
result = []
comparisons = 0
i = 0
j = 0
while i < len(left) and j < len(right):
comparisons += 1
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result, comparisons
print(merge_count([1, 3, 5], [2, 4]))Example
def merge(left, right, counter):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
counter[0] += 1
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
print("merge", left, "and", right, "gives", result)
return result
def merge_sort(values, counter):
if len(values) <= 1:
return values
mid = len(values) // 2
left = merge_sort(values[:mid], counter)
right = merge_sort(values[mid:], counter)
return merge(left, right, counter)
counter = [0]
result = merge_sort([38, 27, 43, 3, 9, 82, 10], counter)
print("sorted:", result)
print("comparisons:", counter[0])Key points
- Merge sort sorts by splitting a list, sorting the halves, and merging them.
- Merging two sorted lists takes one pass through both lists.
- Merge sort builds new lists while merging, so it uses extra memory.
- Each level of splitting cuts every list in half again.
In this example, merge sort splits the list of seven values down to single values. The split halves are sorted by the same function, one call per half. Each merge then joins two sorted runs and prints the joined result. The merges spend 13 comparisons in total, far below a check of every pair. The final line prints the fully sorted list.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
What does merge([2, 5], [1, 9]) return?