Sorting
How Sorting works
Before you start
- Open lesson
Two Pointers
The merge step walks two sorted lists with one pointer each.
Why it matters
Ordered data makes duplicates adjacent, enables fast lookup, and lets databases join large tables predictably. A quadratic sort may look fine on a short list but becomes the bottleneck at production scale. For [5, 2, 3, 1], produce sorted output with O(n log n) worst-case work rather than repeatedly scan the unsorted remainder.
Example
Sort an Array
Return nums sorted in non-decreasing order. Implement a real O(n log n) sort (merge or heap) — do not call the language sort if you can help it. Tests only check the result.
- Input
- nums = [5, 2, 3, 1]
- Output
- [1, 2, 3, 5]
Approach 1 · Brute force
Selection sort
Same example
nums = [5, 2, 3, 1]
Find the smallest value, swap it to the front, and repeat on the rest. Each pass scans everything that is left, so n passes cost about n²/2 comparisons.
Time O(n²) · Space O(1)
- 1def sortArray(nums):
- 2 for i in range(len(nums)):
- 3 low = i
- 4 for j in range(i + 1, len(nums)):
- 5 if nums[j] < nums[low]:
- 6 low = j
- 7 nums[i], nums[low] = nums[low], nums[i]
- 8 return nums
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Sort an Array
nums = [5, 2, 3, 1]→[1, 2, 3, 5]
The baseline, Selection sort, is O(n²) · O(1). The better model below keeps this exact input and removes that bottleneck.
Split [5, 2, 3, 1] into [5, 2] and [3, 1]; after they become [2, 5] and [1, 3], merge them into [1, 2, 3, 5]. Linear merges across log levels replace selection sort's repeated remaining-array scans.
Split [5, 2, 3, 1] into [5, 2] and [3, 1], then split again until each piece has one value. Merging each pair gives [2, 5] and [1, 3]; the one-value pieces need no sorting work.
To merge the two halves, compare their front values: take 1 before 2, then 2 before 3, then 3 before 5, and append 5. Every merge level touches all four values once. More generally, each level costs O(n), and halving creates log₂ n levels.
Split in half
Merge back up
8 values · 3 levels = log₂ 8 · each level merges all 8
Run the same example
Walkthrough
- 1.If the array has one value or none, return it.
- 2.Split at mid and sort each half recursively.
- 3.Merge: repeatedly append the smaller front value of the two halves.
- 4.When one half runs out, append the rest of the other.
Python
Sort an Array
- Input:
- nums = [5, 2, 3, 1]
- Output:
- [1, 2, 3, 5]
- 1def sortArray(nums):
- 2 if len(nums) <= 1:
- 3 return nums
- 4 mid = len(nums) // 2
- 5 left = sortArray(nums[:mid])
- 6 right = sortArray(nums[mid:])
- 7 merged = []
- 8 i = j = 0
- 9 while i < len(left) and j < len(right):
- 10 if left[i] <= right[j]:
- 11 merged.append(left[i])
- 12 i += 1
- 13 else:
- 14 merged.append(right[j])
- 15 j += 1
- 16 merged.extend(left[i:])
- 17 merged.extend(right[j:])
- 18 return merged
nums
Split at mid = 2. Sort the left half and the right half on their own, then merge them.
Complexity
TimeO(n log n)
SpaceO(n)
Each level of recursion merges n values in total, and halving gives log n levels, so time is O(n log n) in every case. The halves and merged lists hold O(n) values at a time, plus O(log n) for the call stack.
Where this breaks
Merge sort's levels assume you can split and merge freely. A sort that must stay in place with a few extra slots wants a different algorithm.
Brute force
Selection sort
O(n²) time
O(1) space
This technique
Merge sort
O(n log n) time
O(n) space
n=100
n=1,000
n=10,000
Comparisons on a log scale. At 10,000 values merge sort does about 375 times less work.
Your turn
Sort an Array
Same problem, your code.
Solve Sort an ArrayThen branch out
Same technique, different problems. Try them without the walkthrough.