n log n is the win
Splitting halves the row each level, and there are about log levels. Each level costs n, so the total is n log n, which for a million items is far under a million squared.
Merge sort
Merge sort splits the row in half, sorts each half, then merges the two ordered halves. Splitting means the work is n log n, far better than n squared.
What you will see
4
About 3 min of reading
Quick check
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Try It
Run merge sort and its merge step.
1
Merge two ordered rows.
left = [2, 5]
right = [1, 8]
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out += left[i:]
out += right[j:]
print(out)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[1, 2, 5, 8]
2
Sort a row with merge sort.
def msort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
L = msort(a[:mid])
R = msort(a[mid:])
out = []
i = j = 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
out.append(L[i]); i += 1
else:
out.append(R[j]); j += 1
return out + L[i:] + R[j:]
print(msort([5, 2, 8, 1]))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[1, 2, 5, 8]
3
Show the split of four.
nums = [5, 2, 8, 1]
mid = len(nums) // 2
print(nums[:mid], nums[mid:])
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[5, 2] [8, 1]
4
Count the split depth of eight.
print(len([1, 2, 3, 4, 5, 6, 7, 8]).bit_length())
Before you run it, say out loud what it will print. Then open the answer.
What it prints
4
Data Flow
Merge sort splits the row, sorts each half, and merges ordered halves in linear time, giving n log n overall.
1
split in half
↓
2
sort each half
↓
3
merge two ordered rows
↓
4
n log n total
Line by line
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
left = [2, 5]
sets nothing on screen
right = [1, 8]
sets nothing on screen
out = []
sets nothing on screen
i = j = 0
sets nothing on screen
while i < len(left) and j < len(right):
sets nothing on screen
if left[i] <= right[j]:
sets nothing on screen
out.append(left[i]); i += 1
sets nothing on screen
else:
sets nothing on screen
out.append(right[j]); j += 1
sets nothing on screen
out += left[i:]
sets nothing on screen
out += right[j:]
sets nothing on screen
print(out)
[1, 2, 5, 8]
Why this works
When you have a choice
Trade-off is memory
Merge sort is fast and stable but needs room for the merged rows. When memory is tight, an in-place sort is chosen instead.
Examples
Split in half
nums = [5, 2, 8, 1]
mid = len(nums) // 2
print(nums[:mid], nums[mid:])The row splits into two halves. Each half is sorted on its own, then the two are joined.
Merge two ordered rows
left = [2, 5]
right = [1, 8]
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out += left[i:]
out += right[j:]
print(out)Take the smaller front each time. Two ordered rows merge into one ordered row in one pass.
Full merge sort
def msort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
L = msort(a[:mid])
R = msort(a[mid:])
out = []
i = j = 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
out.append(L[i]); i += 1
else:
out.append(R[j]); j += 1
return out + L[i:] + R[j:]
print(msort([5, 2, 8, 1]))Sort each half, then merge. The <= keeps equal items in order, so it is stable.
The base case
print([7])A row of one is already sorted. That is where the splitting stops, the bottom of the tree.
Halving the depth
print(len([1, 2, 3, 4, 5, 6, 7, 8]).bit_length())Eight items split three times to reach singles. The number of splits grows slowly, which is the log part.
Merge is linear
left = [1, 3]
right = [2, 4]
print(len(left) + len(right))Merging touches each item once. Linear merge times log splits is n log n.
Stable by <=
left = [[2, "a"]]
right = [[2, "b"]]
print(left[0] <= right[0])Using <= takes the left item first on a tie. That keeps the halves in order, so the sort is stable.
Extra space
nums = [3, 1]
print(sorted(nums))Merge sort builds new rows while merging. It uses extra memory, unlike an in-place swap sort.
Words this lesson uses
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← Stability and ties
Previous Lesson
Stability and ties