Sorting II (Merge, Quick, Bucket, Cyclic)

Sorting II (Merge, Quick, Bucket, Cyclic) | Algoryva

Intuition

Sorting a huge pile of exam papers

Imagine 1,000 exam papers to sort by score. Inserting them one at a time into a sorted pile means searching and shifting through a growing pile, and it gets slower and slower. A much faster way: split the pile among friends, let each sort their own small pile, then merge two sorted piles by repeatedly taking the smaller top paper. Merging is quick because both piles are already in order.

That is merge sort. Quicksort splits differently: pick one paper as a benchmark and split the rest into “lower” and “higher”, then sort each half. And if scores are whole numbers from 0 to 100, you can skip comparing entirely: just count how many papers have each score.

First, the naive way

Insertion sort at scale

Insertion sort slides each item left into place. It is simple and fast on nearly sorted data, but on reversed data every item moves past all the others.

The counter below counts shifts. For the 6 items shown it is 8 (one shift per out-of-order pair, the inversion count); for 1,000 items in reverse order it is 499,500, which is n(n − 1)/2. Double the input and the work quadruples; for 10⁵ items it would be about 5 billion.

python

def insertion_sort(a):
    a = a[:]
    steps = 0
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
            steps += 1
        a[j + 1] = x
    return a, steps

print(insertion_sort([5, 2, 4, 1, 6, 3]))   # ([1, 2, 3, 4, 5, 6], 8)
print(insertion_sort(list(range(1000, 0, -1)))[1])   # 499500

Cost: O(n²) in the worst case: about 10¹⁰ steps for n = 10⁵.

The observation

Sorted halves are cheap to combine

Merging two sorted lists of total size n takes only n steps: look at the two front items, take the smaller, repeat. So if you can sort two halves, you can sort the whole in n extra steps. Sorting each half uses the same idea, recursively, so the list is halved about log₂ n times and every level costs n in total: n log n.

Quicksort gets the same shape differently: one pass (partition) puts everything smaller than a pivot on its left and everything larger on its right, so the pivot is in its final place and the two sides are independent subproblems. If the pivot splits roughly in half each time, that is again log n levels of n work.

The concept

Vocabulary and the n log n barrier

A few ideas organise the whole topic.

Divide and conquer: split the problem, solve the parts independently, combine. Merge sort does the work in the combine step (merging); quicksort does it in the split step (partitioning).
Comparison sort: learns about the data only by asking “is this item before that one?”. Any such algorithm needs about n log₂ n comparisons in the worst case, because each comparison has only two outcomes and there are n! possible orders to tell apart (log₂ n! is about n log₂ n).
Beating the barrier: counting, bucket and cyclic sort use extra knowledge about the values (small integers, a uniform spread, or exactly 1 to n), so they do not need comparisons.
Stable: equal items keep their original order. Merge sort is stable; quicksort as written is not.
In place: uses only O(1) or O(log n) extra memory beyond the input. Quicksort and cyclic sort are; merge sort needs O(n) extra.

See it move

Merge sort in motion

Blue is the left sorted half, red is the right. At each merge the pointers i and j compare front items and the smaller moves into “merged so far”. Watch the small merges at the bottom combine into bigger ones, level by level.

See it move

Quicksort's partition step

Quicksort picks a pivot, here the last element, and moves smaller values to its left. The pivot ends in its final position, and both sides are then sorted the same way. Watch the i pointer mark the end of the left block as j scans the rest.

Worked by hand

One merge by hand

Merge the sorted halves [2, 4, 5] and [1, 3, 6].

compare	take	merged so far
2 vs 1	1 (right)	[1]
2 vs 3	2 (left)	[1, 2]
4 vs 3	3 (right)	[1, 2, 3]
4 vs 6	4 (left)	[1, 2, 3, 4]
5 vs 6	5 (left)	[1, 2, 3, 4, 5]
left empty	6 (rest of right)	[1, 2, 3, 4, 5, 6]

1
Each step takes one item
Six items, six steps: the cost of a merge is the total size, never more.
2
Why <= matters
Taking from the left on ties keeps equal items in their original order, which makes merge sort stable.

Implementation

Merge sort in code

Split, sort each half recursively, merge.

Plan in plain steps

pseudocode

merge_sort(list):
    if the list has 0 or 1 items: return it
    split into left and right halves; sort each recursively
    merge: repeatedly take the smaller front item; then append whatever remains

python

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out = []
    i = j = 0
    while i < len(left)  j < (right):
         left[i] <= right[j]:
            out.(left[i])
            i += 
        :
            out.(right[j])
            j += 
    out.(left[i:])
    out.(right[j:])
     out

(([, , , , , ]))   
(([]), ([]))   
(([, , , , ]))

Implementation

Quicksort with a random pivot

Partition around a pivot in place. Using a random pivot makes the bad case (always picking the smallest or largest) astronomically unlikely, whatever the input.

python

import random

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    p = random.randint(lo, hi)
    a[p], a[hi] = a[hi], a[p]
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    quicksort(a, lo, i - 1)
    quicksort(a, i + 1, hi)

data = [5, 2, , , , , ]
(data)
(data)   
empty = []
(empty)
(empty)   
random.()
big = [random.(, )  _  ()]
check = big[:]
(check)
(check == (big))

Implementation

Beating n log n: counting and bucket sort

Comparison sorts cannot beat about n log n. If you do not compare, you can. Counting sort tallies how many times each small integer appears and then writes them out in order. Bucket sort drops values into a few ranges, sorts each small bucket, and joins them.

python

def counting_sort(a, max_val):
    cnt = [0] * (max_val + 1)
    for x in a:
        cnt[x] += 1
    out = []
    for v, c in enumerate(cnt):
        out.extend([v] * c)
    return out

print(counting_sort([3, 1, 4, 1, 5, 2, 0], 5))   # [0, 1, 1, 2, 3, 4, 5]

def bucket_sort(a, buckets=4):
    lo, hi = min(a), max(a)
    width = (hi - lo) / buckets  
    bins = [[]  _  (buckets)]
     x  a:
        bins[(((x - lo) / width), buckets - )].(x)
    out = []
     b  bins:
        out.((b))
     out

(([, , , , , ]))

See it move

Cyclic sort: every value goes home

When an array holds the numbers 1 to n, the value v belongs at index v − 1. Look at the value under pointer i: if its home already holds the right value, move on; otherwise swap it home. Every swap puts at least one value in its final spot, so there are at most n swaps.

Implementation

Cyclic sort, and what it finds

Sorting 1 to n in O(n) time and O(1) space is useful on its own, and even more as a way to spot what does not fit: after cyclic sort, an index i that does not hold i + 1 reveals a missing number (i + 1), and the value found there is a duplicate.

python

def cyclic_sort(a):
    i = 0
    while i < len(a):
        j = a[i] - 1
        if a[i] != a[j]:
            a[i], a[j] = a[j], a[i]
        else:
            i += 1
    return a

print(cyclic_sort([3, 1, 5, 4, 2]))   # [1, 2, 3, 4, 5]
print(cyclic_sort([2, 3, 4, 1, 1]))   # [1, 2, 3, 4, 1]

Reading the code

›j = a[i] - 1 is the home index of the current value.
›

Implementation

Missing and duplicate numbers

Two classic uses: the smallest missing positive number (values can be anything), and finding the duplicate and the missing number in a list that should be 1 to n.

python

def first_missing_positive(a):
    n = len(a)
    i = 0
    while i < n:
        j = a[i] - 1
        if 0 <= j < n and a[i] != a[j]:
            a[i], a[j] = a[j], a[i]
        else:
            i += 1
    for i in range(n):
        if a[i] != i + 1:
            return i + 1
    return n + 1

print(first_missing_positive([3, 4, -1, 1]))   
(([, , , , ]))   
(([, , ]))   

 (a):
    n = (a)
    a = a[:]
    i = 
     i < n:
        j = a[i] - 
         a[i] != a[j]:
            a[i], a[j] = a[j], a[i]
        :
            i += 
     i  (n):
         a[i] != i + :
             [a[i], i + ]
     []

(([, , , ]))   
(([, ]))

Complexity

Costs side by side

Any algorithm that sorts only by comparing items needs at least about n log₂ n comparisons in the worst case, so merge sort is optimal among comparison sorts. The non-comparison sorts beat it by using extra knowledge about the values.

Merge sort

time O(n log n) alwaysspace O(n)

log₂ n levels of halving, each level merges n items in total. Stable.

Quicksort (random pivot)

time O(n log n) expected, O(n²) worstspace O(log n) stack

Balanced partitions give log n levels; the worst case needs repeatedly terrible pivots, which random choice makes extremely unlikely. Not stable.

Counting sort

time O(n + k)space O(k)

One pass to count, one to write out; k is the value range.

Bucket sort

time O(n) on evenly spread data, O(n²) worstspace O(n)

Small buckets sort cheaply; one crowded bucket does not.

Cyclic sort (values 1..n)

time O(n)space O(1)

At most n swaps, each placing a value permanently.

Insertion / selection / bubble

time O(n²)space O(1)

Compare or shift against many other items for each item.

Count inversions with merge sort

Edge cases

Empty or one-item listAlready sorted. Base cases len <= 1 and lo >= hi handle it.
Many equal keysMerge sort is unaffected. Simple quicksort partitions degrade; use a three-way partition if equal keys are common.
Already sorted inputA quicksort that always picks the first or last item as pivot goes quadratic. Random pivot avoids that.
Counting sort with huge valuesMemory is O(max value). Only use it when the range is modest (say up to a few million).
Negative numbers in counting sortShift by the minimum value so indices start at 0.
Cyclic sort with values outside 1..nSkip them (as first_missing_positive does); an out-of-range index would crash.
Recursion depthMerge sort is only log n deep. Quicksort can be deep on bad pivots; random pivots keep it shallow.

Common mistakes

Mistakes to avoid

Writing your own sort when sorted would do.
In contests use the built-in. Write these to learn, or when a problem needs the merge step itself (inversions, counting pairs).
Merging with < instead of <=.
Use <= on ties so the sort stays stable and counts of “pairs with equal values” come out right.
Infinite loop in cyclic sort with duplicates.
Swap only if a[i] != a[j]; otherwise advance i.
Always picking the first element as the quicksort pivot.
Pick randomly (or the median of three).
Using counting sort on a wide range.
Compare k with n log n: counting sort needs k to be comparable to n.

Recognize it in a contest

How to spot which sort to reach for

Reach for it when the problem says or implies

You just need sorted output: use the built-in (sorted, .sort()).
A problem asks for inversions, “count of smaller elements after self”, or pairs satisfying an inequality between positions: merge sort with counting during the merge.
The array holds the numbers 1 to n (or values that can be mapped there), and you must find missing, duplicate or misplaced values in O(1) extra space: cyclic sort.
Values are small integers or fall in a small range: counting sort.
Values are real numbers spread uniformly in a range: bucket sort.
You must sort a linked list in O(n log n): merge sort (merging linked lists needs no extra memory).

Look elsewhere when

Worked problem

Count inversions

The problem

An inversion is a pair of positions i < j with a[i] > a[j]. Count all inversions in an array in O(n log n). (Brute force over every pair is O(n²).)

Run merge sort. Inversions come in three kinds: both items in the left half, both in the right half, or one in each.
The first two are counted by the recursive calls. For the third, use the merge: both halves are sorted, so when a right item is smaller than the current left item, it is also smaller than every item still waiting in the left half.
So each time a right item is taken, add the number of left items remaining: len(left) - i.

python

def count_inversions(a):
    def sort(lst):
        if len(lst) <= 1:
            return lst, 0
        mid = len(lst) // 2
        left, x = sort(lst[:mid])
        right, y = sort(lst[mid:])
        merged, count = [], x + y
        i = j = 0
         i < (left)  j < (right):
             left[i] <= right[j]:
                merged.(left[i])
                i += 
            :
                merged.(right[j])
                j += 
                count += (left) - i
        merged.(left[i:])
        merged.(right[j:])
         merged, count
     (a)[]

(([, , , , ]))   
(([, , , , ]))   
(([, , ]))

Worked problem

Find the missing number and the duplicate

The problem

A list should contain 1 to n once each, but one number appears twice and another is missing. Return [duplicate, missing] in O(n) time and O(1) extra space.

Use cyclic sort: swap each value to its home index value − 1, skipping when its home already holds the same value.
Afterwards every value is home except the duplicate's extra copy, which sits in the slot belonging to the missing number.
The one index i where a[i] != i + 1 gives both answers: a[i] is the duplicate and i + 1 is the missing number.

python

def first_missing_positive(a):
    n = len(a)
    i = 0
    while i < n:
        j = a[i] - 1
        if 0 <= j < n and a[i] != a[j]:
            a[i], a[j] = a[j], a[i]
        else:
            i += 
     i  (n):
         a[i] != i + :
             i + 
     n + 

(([, , -, ]))   
(([, , , , ]))   
(([, , ]))   

 (a):
    n = (a)
    a = a[:]
    i = 
     i < n:
        j = a[i] - 
         a[i] != a[j]:
            a[i], a[j] = a[j], a[i]
        :
            i += 
     i  (n):
         a[i] != i + :
             [a[i], i + ]
     []

(([, , , ]))   
(([, ]))

Wrap-up

Remember this

Simple sorts are O(n²); merge sort and quicksort reach O(n log n) by dividing the problem.
Merging two sorted lists costs only their total size, which is why halving repeatedly gives n log n.
Quicksort partitions around a pivot in place; a random pivot avoids the quadratic worst case.
Counting and bucket sort beat n log n by not comparing, when values are small or evenly spread.
Cyclic sort handles arrays of 1 to n in O(n) time and O(1) space; merge sort can count inversions while it sorts.

Cheat sheet

Merge sort: split, sort halves, merge by taking the smaller front; O(n log n), stable, O(n) space
Quicksort: random pivot, partition, recurse on both sides; O(n log n) expected, in place, not stable
Counting sort: count each value, write out in order; O(n + k)
Cyclic sort: swap a[i] to index a[i] − 1 unless already equal; O(n), O(1) space
Inversions: during the merge, add len(left) − i when taking from the right
Lower bound: comparison sorts need Ω(n log n)

Top traps to avoid

Writing your own sort when sorted would do.
Merging with < instead of <=.
Infinite loop in cyclic sort with duplicates.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Why does merge sort run in O(n log n)?
2.Merge [2, 4, 5] and [1, 3, 6]. What is the second item taken?
3.Why does a random pivot help quicksort?
4.An array holds the numbers 1 to n with one missing and one repeated. Which technique finds both in O(n) time and O(1) space?
5.count_inversions([2, 4, 1, 3, 5]) returns 3. Which pairs are the inversions?
6.When is counting sort a poor choice?
7.What is the running time of merge sort on n items?
8.Lomuto partition with pivot = last element, on a = [3, 1, 2]. What is printed? p = a[-1]; i = 0; for j in range(len(a)-1): if a[j] < p: swap a[i], a[j]; i += 1; then swap a[i], a[-1]
9.Counting sort on [3, 1, 3, 0] (keys 0 to 3). What is the result?
10.Cyclic sort on [3, 1, 2] (values 1 to n). What is printed? i = 0; while i < n: j = a[i]-1; if a[i] != a[j]: swap a[i], a[j] else: i += 1
11.Why can quicksort degrade to O(n²), and what prevents it in practice?
12.Which sort is both stable and O(n log n) in the worst case?
13.Counting sort on n items with keys from 0 to k: what is the time?
14.Python sorts (1,'b'), (0,'z'), (1,'a') by the first item only. What is the result?
15.Merge sort splits [5, 2, 9] into [5] and [2, 9], then sorts and merges. What is the final list?

Sorting II (Merge, Quick, Bucket, Cyclic)

After this lesson you will be able to

Builds on

Unlocks

Sorting a huge pile of exam papers

Insertion sort at scale

Sorted halves are cheap to combine

Vocabulary and the n log n barrier

Merge sort in motion

Quicksort's partition step

One merge by hand

Merge sort in code

Quicksort with a random pivot

Beating n log n: counting and bucket sort

Cyclic sort: every value goes home

Cyclic sort, and what it finds

Reading the code

Missing and duplicate numbers

Costs side by side

Edge cases

Mistakes to avoid

How to spot which sort to reach for

Count inversions

Find the missing number and the duplicate

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core45 problems

Application11 problems

Challenge1 problem

Reading the code

Reading the code

Reading the code

Reading the code