Merging and Partitioning

26 min · Intermediate

Sorted data arrives in pieces all the time: daily sales from two branches, two lists of ticket ids. This lesson shows how to join them in one pass and how to separate items by kind without a full sort.

Merge two sorted lists

Merge means combining two sorted lists into one sorted list by repeatedly taking the smaller front item. It takes O(n + m) time because each item is looked at once.

Two branches send daily sales, each list already sorted. Merge them in one pass: compare the front items, take the smaller one, and move that list's pointer forward.

Python

1a = [1, 4, 9]2b = [2, 3, 10, 12]3i = j = 04merged = []5while i < len(a) and j < len(b):6    if a[i] <= b[j]:7        merged.append(a[i])8        i += 19    else:10        merged.append(b[j])11        j += 112merged += a[i:]13merged += b[j:]14print(merged)

Example 1 · Merge with repeated values

Python

1def merge_sorted(a, b):2    i = j = 03    merged = []4    while i < len(a) and j < len(b):5        if a[i] <= b[j]:6            merged.append(a[i])7            i += 18        else:9            merged.append(b[j])10            j += 111    return merged + a[i:] + b[j:]12
13
14print(merge_sorted([1, 2, 2, 5], [2, 3]))

Output

[1, 2, 2, 2, 3, 5]

What this code does

<= takes from the first list on a tie, so equal items keep their original order.
The leftovers are added with slices, which are empty when a list is used up.
O(n + m) time and O(n + m) space for the result.

When one list runs out, the rest of the other list is already in order, so it is added as it is. Time is O(n + m).

Brute force and the built-ins

The shortest way is sorted(a + b). It ignores that the inputs are sorted and costs O(n log n). heapq.merge does the one-pass merge lazily. Interviews expect you to write the pointer version by hand.

Python

1from heapq import merge2
3a = [1, 4, 9]4b = [2, 3, 10, 12]5print(sorted(a + b))6print(list(merge(a, b)))

Example 2 · Merge many sorted lists with heapq

Python

1from heapq import merge2
3north = [3, 8, 20]4south = [1, 9]5east = [4, 5, 6]6print(list(merge(north, south, east)))

Output

[1, 3, 4, 5, 6, 8, 9, 20]

What this code does

merge takes any number of sorted inputs.
It yields items one at a time, so it works well with very large inputs.
It does not sort: unsorted input gives a wrong result.

Both give the same answer. merge also accepts more than two sorted inputs.

Merge from the back, in place

A list nums1 has empty room at its end for the items of nums2. Fill it from the largest end, so no item you still need is overwritten.

Python

1nums1 = [2, 5, 8, 0, 0, 0]2nums2 = [1, 6, 9]3i, j, k = 2, 2, 54while j >= 0:5    if i >= 0 and nums1[i] > nums2[j]:6        nums1[k] = nums1[i]7        i -= 18    else:9        nums1[k] = nums2[j]10        j -= 111    k -= 112print(nums1)

Example 3 · Merge into nums1 as a function

Python

1def merge_in_place(nums1, m, nums2, n):2    i, j, k = m - 1, n - 1, m + n - 13    while j >= 0:4        if i >= 0 and nums1[i] > nums2[j]:5            nums1[k] = nums1[i]6            i -= 17        else:8            nums1[k] = nums2[j]9            j -= 110        k -= 111
12
13first = [4, 5, 6, 0, 0, 0]14merge_in_place(first, 3, [1, 2, 3], 3)15print(first)16empty = [0]17merge_in_place(empty, 0, [7], 1)18print(empty)

Output

[1, 2, 3, 4, 5, 6]
[7]

What this code does

m and n say how many real items each list has.
The second call has nothing real in nums1, so everything comes from nums2.
O(m + n) time and O(1) extra space.

k is the next free slot from the back. When nums2 is used up, the remaining front items of nums1 are already in place.

Partition: sort colours in one pass

Partition means rearranging a list so that items of one kind come before items of another kind. No full sort is needed, and one pass is often enough.

Orders carry a priority 0, 1 or 2. Sort them in one pass with three pointers: low is the next place for a 0, high the next place for a 2, and mid scans. This is the Dutch national flag problem.

Python

1colors = [2, 0, 2, 1, 1, 0]2low, mid, high = 0, 0, len(colors) - 13while mid <= high:4    if colors[mid] == 0:5        colors[low], colors[mid] = colors[mid], colors[low]6        low += 17        mid += 18    elif colors[mid] == 1:9        mid += 110    else:11        colors[mid], colors[high] = colors[high], colors[mid]12        high -= 113print(colors)

Example 4 · Sort colours by counting

Python

1from collections import Counter2
3colors = [2, 0, 2, 1, 1, 0]4count = Counter(colors)5colors[:] = [0] * count[0] + [1] * count[1] + [2] * count[2]6print(colors)

Output

[0, 0, 1, 1, 2, 2]

What this code does

A first pass counts each value and a second pass rewrites the list.
Two passes, O(n) time and O(1) extra space, because there are only three values.
The three-pointer version does the same in one pass.

Example 5 · Even numbers first with two pointers

Python

1orders = [3, 8, 5, 2, 7, 4]2left, right = 0, len(orders) - 13while left < right:4    if orders[left] % 2 == 0:5        left += 16    elif orders[right] % 2 == 1:7        right -= 18    else:9        orders[left], orders[right] = orders[right], orders[left]10        left += 111        right -= 112print(orders)

Output

[4, 8, 2, 5, 7, 3]

What this code does

left skips even items and right skips odd items.
When left holds an odd item and right an even one, they swap.
The order inside each group may change. That is fine for a partition.

After a swap with high, mid stays, because the item that arrived has not been checked yet. One pass, O(1) extra space.

Next step

Check your understanding

12 quick questions

Merge two sorted lists

Merge means combining two sorted lists into one sorted list by repeatedly taking the smaller front item. It takes O(n + m) time because each item is looked at once.

Two branches send daily sales, each list already sorted. Merge them in one pass: compare the front items, take the smaller one, and move that list's pointer forward.

1a = [1, 4, 9]2b = [2, 3, 10, 12]3i = j = 04merged = []5while i < len(a) and j < len(b):6 if a[i] <= b[j]:7 merged.append(a[i])8 i += 19 else:10 merged.append(b[j])11 j += 112merged += a[i:]13merged += b[j:]14print(merged)

1def merge_sorted(a, b):2 i = j = 03 merged = []4 while i < len(a) and j < len(b):5 if a[i] <= b[j]:6 merged.append(a[i])7 i += 18 else:9 merged.append(b[j])10 j += 111 return merged + a[i:] + b[j:]12 13 14print(merge_sorted([1, 2, 2, 5], [2, 3]))

1nums1 = [2, 5, 8, 0, 0, 0]2nums2 = [1, 6, 9]3i, j, k = 2, 2, 54while j >= 0:5 if i >= 0 and nums1[i] > nums2[j]:6 nums1[k] = nums1[i]7 i -= 18 else:9 nums1[k] = nums2[j]10 j -= 111 k -= 112print(nums1)

1def merge_in_place(nums1, m, nums2, n):2 i, j, k = m - 1, n - 1, m + n - 13 while j >= 0:4 if i >= 0 and nums1[i] > nums2[j]:5 nums1[k] = nums1[i]6 i -= 17 else:8 nums1[k] = nums2[j]9 j -= 110 k -= 111 12 13first = [4, 5, 6, 0, 0, 0]14merge_in_place(first, 3, [1, 2, 3], 3)15print(first)16empty = [0]17merge_in_place(empty, 0, [7], 1)18print(empty)

Partition: sort colours in one pass

Partition means rearranging a list so that items of one kind come before items of another kind. No full sort is needed, and one pass is often enough.

Orders carry a priority 0, 1 or 2. Sort them in one pass with three pointers: low is the next place for a 0, high the next place for a 2, and mid scans. This is the Dutch national flag problem.

1colors = [2, 0, 2, 1, 1, 0]2low, mid, high = 0, 0, len(colors) - 13while mid <= high:4 if colors[mid] == 0:5 colors[low], colors[mid] = colors[mid], colors[low]6 low += 17 mid += 18 elif colors[mid] == 1:9 mid += 110 else:11 colors[mid], colors[high] = colors[high], colors[mid]12 high -= 113print(colors)

1orders = [3, 8, 5, 2, 7, 4]2left, right = 0, len(orders) - 13while left < right:4 if orders[left] % 2 == 0:5 left += 16 elif orders[right] % 2 == 1:7 right -= 18 else:9 orders[left], orders[right] = orders[right], orders[left]10 left += 111 right -= 112print(orders)