TweakCode
FREE
Search lessons

Sorting · Stage 1 of 3

Comparison Sorting & Adjacent Sweeps

Order elements so global comparisons become adjacent checks

Foundations

Sorting arranges an array so nums[0] <= nums[1] <= ... <= nums[n - 1]. A comparison sort learns that order only by comparing two elements at a time, and none can beat O(n log n) comparisons in the worst case. Merge sort meets that bound: split the array in half, sort each half the same way, then merge the two sorted halves by repeatedly taking the smaller front element. One element alone is already sorted.

Split in half

52819374
5281
9374
52
81
93
74
5
2
8
1
9
3
7
4

Merge back up

5
2
8
1
9
3
7
4
25
18
39
47
1258
3479
12345789

8 values · 3 levels = log₂ 8 · each level merges all 8

Eight values split into halves until each piece holds one value, then merge back up. There are three levels, and each level's merges handle all eight values once.

Order is transitive: if every neighbor pair has nums[i] <= nums[i + 1], then every pair is in order. So once an array is sorted, many questions about all pairs need only neighbors. Equal values sit side by side, and the two closest values are always adjacent. One sweep over the n - 1 neighbor pairs, O(n), replaces checking all n(n - 1) / 2 pairs.

Merge sort splits nums = [7, 1, 5, 3, 6] into [7, 1] and [5, 3, 6], sorts them into [1, 7] and [3, 5, 6], and merges those into [1, 3, 5, 6, 7]. To find the two closest values, checking every pair takes 10 comparisons. In sorted order only neighbors can be closest, so a sweep reads 4 gaps, 2, 2, 1, and 1: the closest values are 5 and 6.

nums, sorted

01234
1
3
5
6
7

gap to next

01234
2
2
1
1
·
Sorted, each value's closest value sits beside it, so 4 neighbor gaps cover all 10 pairs. The smallest gap, 1, is between 5 and 6.

  • Two Pointers

    The merge step walks two sorted lists with one pointer each.

    Open lesson

Case Scenario

The problem

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]

Sort an Array asks for the comparison sort itself: return nums in increasing order in O(n log n) time without the built-in sort. Merge sort fits, because even its worst case is O(n log n). For nums = [5, 2, 3, 1], it splits into [5, 2] and [3, 1], sorts them into [2, 5] and [1, 3], and one merge gives [1, 2, 3, 5].

The direct approach is selection sort: find the smallest remaining element, swap it to the front, and repeat. Each pass rescans everything left, so n elements cost n(n - 1) / 2 comparisons: 6 here, and about 5 billion at n = 100,000. Nothing a pass learns about the order is kept, so the next pass compares the same elements again.

Approach 1 · Brute force

Selection sort

Pass i scans indexes i + 1 to n - 1 for the smallest value and swaps it into slot i. After the pass, slots 0 to i are final.

Time O(n²) · Space O(1)

  1. 1def sortArray(nums):
  2. 2 for i in range(len(nums)):
  3. 3 low = i
  4. 4 for j in range(i + 1, len(nums)):
  5. 5 if nums[j] < nums[low]:
  6. 6 low = j
  7. 7 nums[i], nums[low] = nums[low], nums[i]
  8. 8 return nums

Approach 2 · Merge sort

Walkthrough

Same input, now one step at a time. Each frame highlights the line that runs and the values it changes.

  1. 1.If the array has one element or none, return it.
  2. 2.Split at mid = len(nums) // 2 and sort each half recursively.
  3. 3.Merge: repeatedly append the smaller front element of the two halves.
  4. 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]
  1. 1def sortArray(nums):
  2. 2 if len(nums) <= 1:
  3. 3 return nums
  4. 4 mid = len(nums) // 2
  5. 5 left = sortArray(nums[:mid])
  6. 6 right = sortArray(nums[mid:])
  7. 7 merged = []
  8. 8 i = j = 0
  9. 9 while i < len(left) and j < len(right):
  10. 10 if left[i] <= right[j]:
  11. 11 merged.append(left[i])
  12. 12 i += 1
  13. 13 else:
  14. 14 merged.append(right[j])
  15. 15 j += 1
  16. 16 merged.extend(left[i:])
  17. 17 merged.extend(right[j:])
  18. 18 return merged

nums

0123
5
2
3
1

Split at mid = 2. Sort the left half and the right half on their own, then merge them.

1 / 9

The Pattern

The invariant: every call returns its part of the array sorted, and merging two sorted runs yields a sorted run. Splitting stops at single elements, so about log₂ n levels of merging, each touching all n elements once, sort the whole array in O(n log n).

Check it against the walkthrough. [5, 2, 3, 1] split into [5, 2] and [3, 1], and each half came back sorted, [2, 5] and [1, 3]. The last merge compared front values three times, 2 with 1, 2 with 3, and 5 with 3, then appended the rest of [2, 5].

Selection sort compared 6 pairs and kept nothing. Merge sort keeps every sorted run it builds and compares only front elements, so each level costs O(n). Once the array is sorted, any question about pairs, such as duplicates or the smallest gap, becomes one O(n) sweep over neighbors.

Complexity

TimeO(n log n)

SpaceO(n)

Each level of recursion merges n elements 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) elements at a time, plus O(log n) for the call stack.

Brute force

Selection sort

O(n²) time

O(1) space

This technique

Merge sort

O(n log n) time

O(n) space

5k
664
500k
10k
50M
133k

n=100

n=1,000

n=10,000

Selection sortMerge sort

Comparisons on a log scale. At 10,000 values merge sort does about 375 times less work.

When to use this in an interview

  • You need the elements in order, or the prompt forbids the built-in sort.
  • A question about all pairs, such as duplicates or the closest values, gets easier between neighbors.
  • An O(n log n) budget is fine, and a guaranteed worst case matters.

In production

Sort-merge joins in a database

When neither table has a useful index, PostgreSQL can join two tables by sorting both on the join key and walking them side by side: rows with equal keys end up adjacent, so matching them is one sweep instead of comparing every pair. When the rows outgrow work_mem, it sorts runs that fit in memory, writes them to disk, and merges the runs, the walkthrough's merge step at scale.

Where this breaks

Sorted neighbors answer a pair question only when you sorted by the value that question compares. Merge sort also needs O(n) extra memory; a sort that must stay in place wants heapsort instead.

Your turn

Solve it yourself

You have watched merge sort split, merge, and finish in O(n log n). Write it yourself on Sort an Array, then order numbers by a custom comparison in Largest Number, and sweep sorted neighbors in Can Attend Meetings.

  1. 1

    Sort an Array

    Guided · the problem you traced above

    Solve it
  2. 2Largest NumberOn your own · same pattern, no walkthrough
  3. 3Can Attend MeetingsOn your own · same pattern, no walkthrough

Up next · Stage 2 of 3

Two-Pointer Merge PassesCombine two sorted runs in a single O(n + m) scan

Finished this lesson?

Mark it complete when you are ready to move on.