Sorting: invariants, stability and divide-and-conquer

By UK A Level Computer Science · independent study · myAudience

Original textbook concept plate generated with OpenAI imagegen; labels and states checked against the lesson model. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Sorting: invariants, stability and divide-and-conquer

Sorting constructs an ordering while preserving the input multiset: every occurrence must remain, even when values are duplicated. A sorting result that is ordered but drops a duplicate is incorrect. Stability is an additional property: records with equal keys retain their original relative order. It matters when a previous sort or arrival order carries information, such as equal-priority requests. Stability is not the same as determinism, and it is not required for every sorting application; identify which property the contract promises.

Bubble sort compares neighbouring values and swaps an inverted pair. In the supplied version, a pass over positions 0 through end−1 moves a greatest value in that region to end. The already completed suffix is in its final sorted position. Repeating with a smaller end therefore establishes a growing sorted suffix. Swapping only when the left value is strictly greater preserves the order of equal keys. A changed flag stops early if a pass makes no swaps, because every adjacent pair in the remaining region is already ordered.

The unoptimised worst-case comparison count is (n−1)+(n−2)+…+1=n(n−1)/2, giving Θ(n²). This implementation has the same worst-case bound but uses only n−1 comparisons on already sorted input for n≥2, giving Θ(n) best-case time. It sorts a copy, so although the in-place core needs O(1) working state, the supplied function requires Θ(n) additional storage. Reporting O(1) auxiliary space without acknowledging the copy would describe a different program.

Merge sort splits a list into two smaller lists, sorts each, and merges them by choosing the smaller current front element. During merging, the output prefix is ordered and contains exactly the consumed elements of the two inputs. If keys are equal, choose from the left half first to preserve stability. The base cases of zero or one element are already sorted. This is divide-and-conquer: solve smaller instances of the same problem and compose their solutions. A comparison with bubble sort needs the same input size and the same cost model.

At each recursion level, total merging work is Θ(n), and there are Θ(log n) levels, so worst-case time is Θ(n log n). For this copying/slicing implementation, peak additional storage is O(n), including lists and a logarithmic number of frames; cumulative allocation over the whole run can be O(n log n). Peak live storage is different from total allocation traffic. Other representations can change these details. The sortedness proof, multiset proof, stability condition and resource analysis should be assessed independently rather than bundled into “merge sort is better”.

Reading the diagram: The two coloured ones represent distinguishable records with equal key 1: teal arrived earlier than amber. Bubble passes turn [4,1,3,1] into [1,3,1,4], then [1,1,3,4]; the final no-swap comparison gives six comparisons overall. The merge panel sorts each pair and takes the left teal 1 first on equality. Both methods retain all four occurrences and the teal-before-amber order. These colours reveal stability that identical bare integers would hide.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def bubble(values):
"""Stable ascending sort of a copy; return comparison count."""
result = values.copy()
count = 0
for end in range(len(result) - 1, 0, -1):
changed = False
for i in range(end):
count += 1
if result[i] > result[i + 1]:
result[i], result[i + 1] = result[i + 1], result[i]
changed = True
if not changed:
break
return result, count

def merge_sort(values):
"""Stable divide-and-conquer ascending sort; returns a fresh list."""
if len(values) <= 1:
return values.copy()
mid = len(values) // 2
left, right = merge_sort(values[:mid]), merge_sort(values[mid:])
i = j = 0
result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
return result + left[i:] + right[j:]
```

Worked example: Sort [4,1,3,1] with bubble sort and merge sort. Explain duplicate preservation.

Bubble pass end=3 changes the list to [1,3,1,4] after comparisons (4,1),(4,3),(4,1).

Pass end=2 changes it to [1,1,3,4]. Pass end=1 compares the equal 1s without swapping. Total comparisons=3+2+1=6.

Merge sort splits [4,1] and [3,1], obtains [1,4] and [1,3], then merges to [1,1,3,4]. Choosing the left 1 first preserves their original relative order.

Answer: Both outputs are [1,1,3,4]; all four occurrences survive. Bubble makes six comparisons on this input.

Check your understanding: 1. How many comparisons does bubble([1,2,3,4]) make? 2. Why does swapping >= threaten stability? 3. Derive merge-sort work for n=8 and explain why doubling n does not exactly double n log₂n.

Answer: 1. Three, then the no-change pass ends execution. 2. Equal-key records can exchange positions, reversing arrival order. 3. There are three merging levels with eight elements per level, giving proportional merging work 24, apart from constants and base work. At n=16, n log₂n=64 rather than 48; doubling n adds one level, so the ratio is 2(log₂n+1)/log₂n.

Why: A sorted output must also preserve multiplicities. Θ(n²) worst case does not forbid a linear best case. A copying implementation cannot inherit the storage claim of its in-place core. Stability concerns distinguishable records with equal keys; bare integers can conceal a stability defect.