Chapter 05
Sorting techniques
In this chapter
Learning outcomes
Trace six sorting methods, compare stability and auxiliary space, and explain why pivot and gap choices matter.
5.1 Ordering and stability
Sorting arranges records by a key. Ascending integer order is used here. A stable sort preserves the relative order of records with equal keys. If two students have equal marks, a stable sort by marks preserves their earlier order. Stability is not visible when equal integers carry no distinguishing labels.
An in-place algorithm uses little extra array storage, but recursive calls can still consume stack space. Always state the implementation whose cost is being analysed.
5.2 Bubble, selection and insertion sort
Bubble sort compares adjacent elements and swaps out-of-order pairs. In an ascending pass, the largest remaining value reaches the right end. A swapped flag permits early termination when a whole pass makes no swaps. Use a strict comparison to preserve equal-key order.
Selection sort locates the smallest value in the unsorted suffix and swaps it into the next output position. It performs n(n − 1)/2 key comparisons regardless of initial order. The standard swap-based version is not stable: in {2a, 2b, 1}, swapping 1 with 2a leaves the equal keys ordered 2b, 2a.
Insertion sort maintains a sorted prefix. Save the next key, shift larger prefix values right, and fill the resulting gap. It is useful for small or nearly sorted collections.
| Pass | Key inserted | Array after insertion |
|---|---|---|
| Start | — | 5, 2, 4, 6, 1, 3 |
| 1 | 2 | 2, 5, 4, 6, 1, 3 |
| 2 | 4 | 2, 4, 5, 6, 1, 3 |
| 3 | 6 | 2, 4, 5, 6, 1, 3 |
| 4 | 1 | 1, 2, 4, 5, 6, 3 |
| 5 | 3 | 1, 2, 3, 4, 5, 6 |
Step through insertion sort
An unsigned C index cannot become −1. The lab therefore uses j > 0 and compares a[j − 1] before moving left, rather than decrementing an unsigned j past zero.
5.3 Merge sort
Divide the sequence into two halves, sort each recursively, then merge the sorted halves. During merging, compare the first unconsumed element of each half and copy the smaller one. When one half is exhausted, copy the remainder of the other.
[5,2,4,6] → [5,2] and [4,6]
[5,2] → [5] and [2] → [2,5]
[4,6] → [4] and [6] → [4,6]
merge [2,5] with [4,6] → [2,4,5,6]
Each level processes Θ(n) elements and there are Θ(log n) levels. Standard array merge sort therefore takes Θ(n log n) time. Its temporary array requires Θ(n) storage. Taking from the left half first when keys are equal makes the merge stable.
5.4 Quicksort
Choose a pivot, partition values around it, and recursively sort the two remaining partitions. The supplied lab uses the final element as pivot. For {5, 2, 4, 6, 1, 3}, its first partition produces {2, 1, 3, 6, 5, 4}: pivot 3 reaches index 2. The left and right partitions are not yet internally sorted.
Balanced partitions give Θ(n log n) work. Repeated partitions of sizes zero and n − 1 give Θ(n²). Already sorted input is a bad case for this particular last-pivot implementation. Randomised pivoting improves expected behaviour but does not remove the mathematical quadratic worst case. Standard in-place partitioning is not stable.
5.5 Shell sort
Shell sort performs insertion sorts on elements separated by a gap. Later passes reduce the gap, ending with gap 1. A gap of 3 groups indices (0,3,6,…), (1,4,7,…) and (2,5,8,…). Early movement across long distances can reduce work in the final insertion pass.
for gap = n/2, then gap/2, … while gap > 0:
for i = gap through n − 1:
key = a[i]; j = i
while j >= gap and a[j − gap] > key:
a[j] = a[j − gap]; j = j − gap
a[j] = key
There is no single Shell-sort complexity independent of the gap sequence. The simple halving sequence has O(n²) worst-case time. The method uses Θ(1) auxiliary array space and is generally unstable.
5.6 Comparison guide
| Method | Best time | Worst time | Auxiliary space | Stable in described form? |
|---|---|---|---|---|
| Bubble with early exit | Θ(n) | Θ(n²) | Θ(1) | Yes |
| Selection | Θ(n²) | Θ(n²) | Θ(1) | No |
| Insertion | Θ(n) | Θ(n²) | Θ(1) | Yes |
| Merge, standard array | Θ(n log n) | Θ(n log n) | Θ(n) | Yes |
| Quick, last pivot | Θ(n log n) | Θ(n²) | O(n) worst recursion | No |
| Shell, halving gaps | Gap dependent | O(n²) | Θ(1) | No |
Practice
- Trace one bubble pass on
{5, 1, 4, 2}. - Why does insertion sort remain stable when it shifts only values strictly greater than the key?
- Merge
{2, 5, 8}with{1, 5, 9}. Label the two 5s to show stability. - Explain the effect of all-equal input on a two-way last-pivot quicksort. Propose a better partition strategy for many duplicates.
- Compare the number of shifts in insertion sort for sorted and reverse-sorted arrays of length n.
Programming laboratory
Download sorting.c · Contracts and run instructions
Compile this file on its own. Check the empty, boundary and ordinary cases before changing the implementation.
Read the complete C11 program
/* C11. examples. All sorts accept the half-open range [0,n). */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
/* Strict comparisons preserve the order of equal keys. */
static void bubble_sort(int a[], size_t n)
{
for (size_t end = n; end > 1; --end) {
bool swapped = false;
for (size_t j = 1; j < end; ++j) {
if (a[j - 1] > a[j]) {
swap(&a[j - 1], &a[j]); swapped = true;
}
}
if (!swapped) return;
}
}
/* Standard swapping selection sort is not stable. */
static void selection_sort(int a[], size_t n)
{
for (size_t i = 0; i < n; ++i) {
size_t smallest = i;
for (size_t j = i + 1; j < n; ++j)
if (a[j] < a[smallest]) smallest = j;
if (smallest != i) swap(&a[i], &a[smallest]);
}
}
/* Halving gaps: constant auxiliary space, quadratic worst-case time. */
static void shell_sort(int a[], size_t n)
{
for (size_t gap = n / 2; gap > 0; gap /= 2) {
for (size_t i = gap; i < n; ++i) {
int key = a[i]; size_t j = i;
while (j >= gap && a[j - gap] > key) {
a[j] = a[j - gap]; j -= gap;
}
a[j] = key;
}
}
}
static void insertion_sort(int a[], size_t n)
{
for (size_t i = 1; i < n; ++i) {
int key = a[i];
size_t j = i;
while (j > 0 && a[j - 1] > key) {
a[j] = a[j - 1];
--j;
}
a[j] = key;
}
}
/* Caller supplies a temporary array of at least n integers. */
static void merge_sort(int a[], int temp[], size_t n)
{
if (n < 2) return;
size_t mid = n / 2;
merge_sort(a, temp, mid);
merge_sort(a + mid, temp + mid, n - mid);
size_t i = 0, j = mid, k = 0;
while (i < mid && j < n)
temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i < mid) temp[k++] = a[i++];
while (j < n) temp[k++] = a[j++];
for (k = 0; k < n; ++k) a[k] = temp[k];
}
/* Lomuto partition. Last element pivot: sorted/equal inputs give O(n^2). */
static void quick_sort(int a[], size_t n)
{
if (n < 2) return;
int pivot = a[n - 1];
size_t p = 0;
for (size_t j = 0; j + 1 < n; ++j)
if (a[j] < pivot) swap(&a[p++], &a[j]);
swap(&a[p], &a[n - 1]);
quick_sort(a, p);
quick_sort(a + p + 1, n - p - 1);
}
static void check(const int input[], size_t n)
{
int a[16], b[16], c[16], d[16], e[16], f[16], temp[16];
assert(n <= 16);
memcpy(a, input, n * sizeof *a);
memcpy(b, input, n * sizeof *b);
memcpy(c, input, n * sizeof *c);
memcpy(d, input, n * sizeof *d);
memcpy(e, input, n * sizeof *e);
memcpy(f, input, n * sizeof *f);
insertion_sort(a, n); merge_sort(b, temp, n); quick_sort(c, n);
bubble_sort(d, n); selection_sort(e, n); shell_sort(f, n);
for (size_t i = 0; i < n; ++i) {
assert(a[i] == b[i] && b[i] == c[i]);
assert(c[i] == d[i] && d[i] == e[i] && e[i] == f[i]);
assert(i == 0 || a[i - 1] <= a[i]);
}
}
int main(void)
{
int a[] = {5, 2, 4, 6, 1, 3};
int duplicate[] = {3, -1, 3, 0, -1, 8};
int ordered[] = {1, 2, 3, 4, 5};
int reverse[] = {5, 4, 3, 2, 1};
int equal[] = {7, 7, 7, 7};
check(a, 6); check(duplicate, 6); check(ordered, 5);
check(reverse, 5); check(equal, 4); check(a, 1); check(a, 0);
/* Exhaust all ternary arrays of lengths 0..7: 3,280 inputs. */
int generated[7];
size_t combinations = 1;
for (size_t length = 0; length <= 7; ++length) {
for (size_t pattern = 0; pattern < combinations; ++pattern) {
size_t digits = pattern;
for (size_t i = 0; i < length; ++i) {
generated[i] = (int)(digits % 3) - 1; digits /= 3;
}
check(generated, length);
}
combinations *= 3;
}
insertion_sort(a, 6);
printf("Sorted:");
for (size_t i = 0; i < 6; ++i) printf(" %d", a[i]);
putchar('\n');
puts("sorting tests passed");
return 0;
}