9.2 Advanced Sorting: Shell, Merge, and Divide-and-Conquer
Chapter 9 · Advanced Sorting | Prerequisites: Basic Sorting and recursion | Next chapter: Quick, Heap, and Non-Comparative Sorting. This section first explains the gap strategy in Shell sort, then derives merge sort from an invariant of merging, leading to both top-down and bottom-up implementations.
From Short to Long Steps
Insertion sort moves each record only one position to the left at a time. When an element is far from its target position, the same movement repeats many times. Shell sort begins with larger gaps, allowing elements to travel farther before the gap shrinks to 1 and ordinary insertion sort finishes a nearly sorted array.
Merge sort divides the input in two, sorts each half, then merges. The next chapter's quicksort also uses divide and conquer, but partitions first and handles the two sides afterward. The work happens at different stages.
Unified Code Contract
All three functions return new lists without modifying the input, and evaluate key once per element. Input iterators are consumed, while element objects remain shared by reference. Comparisons inspect only sort keys; the original-position field does not break ties. Keys must have a consistent ordering, excluding NaN, and remain unchanged during sorting. Decoration records use Θ(n) auxiliary space and the result list adds Θ(n) output space. The table separately reports sorting-core costs, treating key extraction and comparisons as constant-time.
def _decorate(values, key):
key_function = (lambda item: item) if key is None else key
return [
[key_function(item), index, item]
for index, item in enumerate(values)
]
def _values(records):
return [record[2] for record in records]
def shell_sort(values, key=None):
"""Use Knuth gap Shell sort of a sequence; not guaranteed to be stable."""
records = _decorate(values, key)
n = len(records)
gap = 1
while gap < n // 3:
gap = 3 * gap + 1
while gap >= 1:
for index in range(gap, n):
current = records[index]
hole = index
while hole >= gap and records[hole - gap][0] > current[0]:
records[hole] = records[hole - gap]
hole -= gap
records[hole] = current
gap //= 3
return _values(records)
def _merge_records(left, right):
merged = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if not right[right_index][0] < left[left_index][0]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
merged.extend(left[left_index:])
merged.extend(right[right_index:])
return merged
def merge_sort(values, key=None):
"""Top-down stable merge sort."""
records = _decorate(values, key)
def sort(part):
if len(part) <= 1:
return part
middle = len(part) // 2
left = sort(part[:middle])
right = sort(part[middle:])
return _merge_records(left, right)
return _values(sort(records))
def merge_sort_bottom_up(values, key=None):
"""Bottom-up stable merge sort."""
records = _decorate(values, key)
width = 1
while width < len(records):
merged_pass = []
for left in range(0, len(records), 2 * width):
middle = min(left + width, len(records))
right = min(left + 2 * width, len(records))
merged_pass.extend(
_merge_records(records[left:middle], records[middle:right])
)
records = merged_pass
width *= 2
return _values(records)
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print("shell: ", shell_sort(data))
print("top-down:", merge_sort(data))
print("bottom-up:", merge_sort_bottom_up(data))
print("original:", data)The example prints:
shell: [3, 9, 10, 27, 38, 43, 82]
top-down: [3, 9, 10, 27, 38, 43, 82]
bottom-up: [3, 9, 10, 27, 38, 43, 82]
original: [38, 27, 43, 3, 9, 82, 10]Shell Sort: The Gap Must Be Clearly Defined
This implementation uses the Knuth sequence:
1, 4, 13, 40, ...The algorithm starts at 1, generates 3*gap+1 while gap < n // 3, then works backward through the gaps. This is not always the largest increment below n: for n=14, it starts at 4 rather than 13. For example, when the gap is 4, the indices 0, 4, 8... form one subsequence, and indices 1, 5, 9... form another. Each of these subsequences is sorted using insertion sort.
Data: [9, 8, 3, 7, 5, 6, 4, 1]
After gap=4: [5, 6, 3, 1, 9, 8, 4, 7]; subsequences spaced 4 apart are sorted
After gap=1: a final round of standard insertion sort is performed
Result: [1, 3, 4, 5, 6, 7, 8, 9]Any valid sequence that eventually includes a gap of 1 will complete the sort, but performance depends on the chosen gap sequence. There is no universal tight upper bound on time complexity for shell sort in general. For the Knuth sequence used here, Princeton's textbook provides an upper bound of O(n^(3/2)) on the number of comparisons, this does not imply that other gap sequences achieve the same performance: Elementary Sorts.
The core of shell sort can run in place, with auxiliary space O(1). However, movements across gaps may cross equal elements, so stability is not guaranteed.
Merge Sort: First Prove the Merge
The merge function takes two already-sorted lists. At each step, it only compares the first remaining element from each list:
left = [27, 38, 43]
right = [3, 9, 10, 82]
Take 3, take 9, take 10, take 27, take 38, take 43, then append 82The loop invariant is that merged contains exactly the smallest len(merged) records from the combined inputs, in order. Each cursor points to the first unused record on its side. Once one list is exhausted, the remaining elements from the other list are already in order and can be appended directly.
The condition not right_key < left_key takes the left record whenever the right key is not smaller, using only <. This also takes the left record on a tie. The left half comes from an earlier position in the input, so equal keys maintain their original order, this ensures merge sort is stable.
Top-down: Drawing a Recursion Tree
It's easier to visualize the levels with eight elements:
[8 7 6 5 4 3 2 1]
/ \
[8 7 6 5] [4 3 2 1]
/ \ / \
[8 7] [6 5] [4 3] [2 1]
/ \ / \ / \ / \
[8][7] [6][5] [4][3] [2][1]When n is a power of two, each merge level processes exactly n elements, with log₂ n levels. For general n, there are at most ceil(log₂ n) levels, and element depths remain logarithmic, giving Θ(n log n) time as nonempty input size grows. Empty and single-element inputs take constant work. This derivation associates the number of basic operations with n, without converting it into milliseconds on a specific machine.
The peak live storage for slices, partial results, and merge buffers is O(n), with an O(log n) call stack. Repeated slicing and result creation across all levels allocate Θ(n log n) reference slots cumulatively; they are not all live at once. Reusing an auxiliary array reduces this allocation cost.
Bottom-Up: Width Doubles
The iterative version starts with a run of length 1:
width=1 [8]+[7] [6]+[5] [4]+[3] [2]+[1]
width=2 [7 8]+[5 6] [3 4]+[1 2]
width=4 [5 6 7 8]+[1 2 3 4]
width=8 completeright = min(left + 2 * width, n) Handles the case where the end is not a full group. The bottom-up version eliminates the O(log n) recursive stack, but merging still requires O(n) buffer space; "no recursion" does not mean "in-place."
Princeton's mergesort materials cover top-down, bottom-up, and comparison lower bounds: Mergesort.
Quick Sort Left for the Next Chapter
First inspect a result that satisfies the partition condition. Neither side needs to be internally sorted yet:
Array: [10, 7, 8, 9, 1, 5]
pivot = 5
After partition: [1, 5, 8, 9, 10, 7]Elements to the left of the pivot are less than or equal to it, and elements to the right are greater than or equal to it. The process then recursively applies to both subarrays. For distinct keys, uniform random pivot selection gives expected O(n log n) time. With many duplicates, the partition rule also matters: a naive two-way rule that sends all equal keys to one side can produce bad partitions even with random pivots. The next chapter uses three-way partitioning to skip the equal region. Worst-case O(n²) remains possible. Princeton's quicksort materials treat randomization, handling equal elements, and degenerate partitions as separate topics: Quicksort.
The next chapter implements randomized three-way quicksort, heap sort, counting sort, radix sort, and bucket sort.
Professional Reference
| Algorithm | Time | Auxiliary Space | Stable | Notes |
|---|---|---|---|---|
| Shell (Knuth gap) | Depends on gap sequence; sources provide an upper bound of O(n^(3/2)) | O(1) | No | Long-range movements; final gap equals 1 |
| Merge (top-down) | Θ(n log n) | O(n) buffer + O(log n) stack | Yes | Preserves left order when elements are equal |
| Merge (bottom-up) | Θ(n log n) | O(n) buffer | Yes | No recursive stack |
The public functions on this page create O(n) decorative records and results to avoid modifying input data; this portion should not be silently included in claims about "in-place" core operations.
Library Boundary
Python guarantees stable sorting, and its documentation describes how Timsort uses existing input order. This does not give the same adaptive behavior to this page's fixed-split merge sort: Python Sorting HOWTO.
Java SE 25's Arrays.sort(Object[]) documentation guarantees stability, describing the current implementation as stable and adaptive iterative merge sort. Different implementations exist for primitive arrays. These are versioned API documentation, not theorems stating that "Java language always uses a specific algorithm": Java SE 25 Arrays.
From Long Steps Back to Divide and Conquer
The performance of Shell sort depends on its gap sequence; without a defined increment pattern, we cannot produce a reliable complexity analysis. The core of merge sort lies in merging two sorted sequences, with recursion or iteration determining how the runs are generated. Stability is preserved by preferring the left element when values are equal.
The next chapter will implement random three-way quicksort, heap sort, and non-comparison sorts, and then integrate these guarantees into a unified selection table.