Sorting overview

Overview

What sorting is

Sorting means rearranging a collection of items so they follow a defined order. For numbers that order is usually ascending (smallest first) or descending (largest first). For text it might be alphabetical; for records it might be "by date" or "by price".

You already worked with collections in the Arrays lesson: a block of same-typed values laid out one after another in memory, reached by index. Sorting is one of the most common things you do to an array. Once an array is sorted, many other operations become dramatically faster and simpler.

Why order is so useful

A sorted array unlocks binary search (the next topic, searching): instead of scanning every element, you repeatedly halve the search range, turning an O(n) scan into an O(log n) lookup. Sorted data also makes it trivial to find the minimum/maximum (the ends), to find duplicates (they become neighbours), to merge two datasets, and to present results in a way humans can read.

From idea to terminology

There are many sorting algorithms — step-by-step recipes for producing sorted output. They differ in two main costs:

• Time: how many comparisons and moves they perform as the input grows.
• Space: how much extra memory they need beyond the array itself.

We describe time and space with Big-O notation, which captures how cost grows with the number of items n and ignores constant factors. A few more terms you will meet: a sort is in place if it needs only a constant amount of extra memory, and stable if it preserves the original relative order of items that compare equal. The rest of this lesson defines each algorithm, then shows the practical answer for C: use qsort.

Why it matters

Why this matters in real software

Sorting is everywhere, usually hidden behind a feature you use without thinking:

• Search results, leaderboards, feeds: ranked by relevance, score, or recency.
• Databases: ORDER BY, index building, and join algorithms all rely on sorting.
• Reports and dashboards: invoices by due date, transactions by amount.
• Systems work: deduplication, merging logs, scheduling tasks by priority.

Choosing the wrong algorithm has real consequences. An O(n^2) sort on a 1,000,000-element array does roughly a trillion operations and can take minutes; an O(n log n) sort does about 20 million and finishes in a blink. Understanding the trade-offs lets you reason about performance instead of guessing.

There is also a correctness and safety angle. A subtly wrong comparator can silently corrupt order, and in C an unsafe comparator can even trigger undefined behaviour. Knowing how to write a correct, overflow-free comparator is a real professional skill.

Core concepts

1. Order: ascending, descending, stable

Definition. Ascending order means each element is less than or equal to the next; descending is the reverse. A sort is stable if two elements that compare equal keep their original relative order.

Stability matters when you sort by one key but care about a second. Example: sort employees by department, but within a department keep them in the order you received them (e.g. by hire date). A stable sort preserves that secondary order for free.

Input (by arrival):  (Ann, Sales) (Bob, IT) (Cal, Sales)
Stable sort by dept: (Bob, IT)   (Ann, Sales) (Cal, Sales)   <- Ann still before Cal
Unstable sort:       (Bob, IT)   (Cal, Sales) (Ann, Sales)   <- order of equals may flip

Pitfall. Assuming every sort is stable. Quicksort and heapsort are not stable; mergesort is.

2. Big-O complexity

Definition. Big-O describes how an algorithm's work grows as n grows, ignoring constants and lower-order terms.

 n        O(n log n)        O(n^2)
 10       ~33               100
 100      ~664              10,000
 1,000    ~9,966            1,000,000
 1,000,000 ~20 million      1 trillion

The gap widens fast. For small n (say under ~50) the simple O(n^2) sorts are perfectly fine and sometimes faster due to low overhead. For large n, only O(n log n) is acceptable.

Knowledge check: If algorithm A is O(n^2) and B is O(n log n), is A always slower than B for every input size? (Answer: no — for very small n, constants can make A faster; Big-O describes growth, not exact time.)

3. The simple sorts: bubble and insertion

Bubble sort repeatedly walks the array, swapping adjacent out-of-order pairs, so the largest element "bubbles" to the end each pass.

Pass 1 on [5,3,8,1]:
  compare 5,3 -> swap -> [3,5,8,1]
  compare 5,8 -> ok   -> [3,5,8,1]
  compare 8,1 -> swap -> [3,5,1,8]   (8 is now in place)

Insertion sort grows a sorted region at the front, taking each new element and sliding it left into position — exactly how most people sort a hand of cards.

Both are O(n^2) worst case. Insertion sort is O(n) on already-nearly-sorted data, which is why real libraries use it for small subarrays.

When to use: tiny arrays, teaching, or nearly-sorted data. When NOT to: large unsorted arrays.

Pitfall. Off-by-one loop bounds. The inner loop of bubble sort must stop at n - 1 - i to avoid reading past the array.

4. The fast sorts: merge, quick, heap

• Mergesort splits the array in half, sorts each half, then merges them. Predictable and stable, but needs an extra O(n) buffer.
• Quicksort picks a pivot, partitions elements into "less" and "greater", then recurses. Fast in practice and in place, but a bad pivot on already-sorted data gives O(n^2). Good implementations randomize or median-pick the pivot.
• Heapsort builds a heap then repeatedly extracts the max. Guaranteed O(n log n) with O(1) extra space, but not stable and has higher constant factors.

Knowledge check (predict): Quicksort's average case is O(n log n). What input pattern triggers its O(n^2) worst case if the pivot is always the first element? (Answer: an already-sorted or reverse-sorted array, because each partition removes only one element.)

5. Don't reinvent it: qsort

Definition. qsort is the C standard library's general-purpose sort in <stdlib.h>. It sorts any array given the element size and a comparator function.

It is well-tested, fast, and type-agnostic, so in real C code you almost never write your own sort. The price is that you must supply a correct comparator — and the standard does not guarantee it is stable.

Knowledge check (explain): In your own words, why does qsort need both sizeof(int) and a comparator function instead of just the array?

Syntax notes

The qsort signature

#include <stdlib.h>

void qsort(void *base,        // pointer to the first element
           size_t nmemb,      // number of elements
           size_t size,       // size of ONE element, in bytes
           int (*compar)(const void *, const void *));
//         ^ a function pointer: takes two const void* and returns <0, 0, or >0

The comparator receives pointers to two elements. It must return:

• a negative value if the first should come before the second,
• 0 if they are equal,
• a positive value if the first should come after the second.

int cmp_int(const void *pa, const void *pb) {
    int a = *(const int *)pa;   // cast void* back to int*, then dereference
    int b = *(const int *)pb;
    return (a > b) - (a < b);    // -> -1, 0, or 1 with no overflow
}

The expression (a > b) - (a < b) yields 1, 0, or -1 and never overflows, unlike a - b.

Lesson

What sorting does

Sorting puts data in order. That order is usually ascending (smallest to largest) or descending (largest to smallest).

Common algorithms

Each algorithm has a different speed and memory cost. The notation O(...) (called Big-O) describes how the work grows as the number of items n grows.

• Bubble / insertion sort — O(n²). Slow on large inputs, but fine for small arrays.
• Mergesort — O(n log n). Stable (keeps equal items in their original order). Needs O(n) extra space.
• Quicksort — O(n log n) on average, but O(n²) in the worst case. Works in place (no extra array).
• Heapsort — O(n log n) guaranteed. In place, but not stable.

What to use in real code

In practice, use qsort from <stdlib.h>. It is well tested and fast, so you rarely need to write your own sort.

Code examples

#include <stdio.h>
#include <stdlib.h>

/* Comparator for ascending int order.
   Returns -1, 0, or 1 without the subtraction-overflow bug. */
static int cmp_int_asc(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    return (a > b) - (a < b);
}

/* A tiny insertion sort, shown for learning. O(n^2) but clear. */
static void insertion_sort(int *a, size_t n) {
    for (size_t i = 1; i < n; i++) {
        int key = a[i];          /* element to place into the sorted prefix */
        size_t j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];     /* slide larger elements one step right */
            j--;
        }
        a[j] = key;              /* drop key into its hole */
    }
}

static void print_array(const int *a, size_t n) {
    for (size_t i = 0; i < n; i++) {
        printf("%d%s", a[i], i + 1 < n ? " " : "\n");
    }
}

int main(void) {
    int data[] = {5, 3, 8, 1, 9, 2, 7};
    size_t n = sizeof data / sizeof data[0];   /* element count, not byte count */

    /* Make a copy so we can demonstrate both sorts on the same input. */
    int *copy = malloc(n * sizeof *copy);
    if (copy == NULL) {                        /* always check malloc */
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    for (size_t i = 0; i < n; i++) copy[i] = data[i];

    insertion_sort(data, n);
    printf("insertion_sort: ");
    print_array(data, n);

    qsort(copy, n, sizeof *copy, cmp_int_asc);
    printf("qsort:          ");
    print_array(copy, n);

    free(copy);                                /* release what we allocated */
    return 0;
}

What it does

The program sorts the same seven numbers two ways: with a hand-written insertion sort, and with the library qsort. Both produce ascending order.

Expected output

insertion_sort: 1 2 3 5 7 8 9
qsort:          1 2 3 5 7 8 9

Edge cases

• An empty array (n == 0) or single element (n == 1) is already sorted; both functions handle it because their loops simply do not run.
• Duplicate values are fine; equal elements stay together.
• sizeof *copy (not sizeof copy) is the per-element size; mixing these up is a classic bug — see the mistakes section.

Line by line

Walking through the example

Setup. data holds {5, 3, 8, 1, 9, 2, 7}. n = sizeof data / sizeof data[0] divides the total byte size by one element's size, giving 7. We malloc a copy and check it is not NULL before using it.

Insertion sort trace. The sorted region starts as just a[0]. Each pass takes key = a[i] and slides larger neighbours right until key fits.

After i = 6 the array is fully sorted: 1 2 3 5 7 8 9.

qsort call. qsort(copy, n, sizeof *copy, cmp_int_asc) tells the library: here are n elements starting at copy, each sizeof(int) bytes, and call cmp_int_asc to compare any two. Internally qsort repeatedly hands two element pointers to the comparator and rearranges bytes accordingly.

Inside the comparator. Suppose qsort compares 8 and 1. It passes pa pointing at the 8, pb at the 1. We cast and dereference: a = 8, b = 1. Then (a > b) - (a < b) = 1 - 0 = 1, meaning 8 comes after 1.

Cleanup. free(copy) returns the heap memory we requested. data was a local array, not heap memory, so it is not freed.

Common mistakes

Mistake 1: comparator subtraction overflow

/* WRONG: can overflow for extreme values */
int cmp(const void *pa, const void *pb) {
    return *(const int *)pa - *(const int *)pb;
}

Why it is wrong: if pa points at INT_MIN and pb at a large positive value, the subtraction overflows. Signed integer overflow is undefined behaviour in C, and even when it does not crash, the sign of the result can flip, sorting things backwards.

/* CORRECT */
int cmp(const void *pa, const void *pb) {
    int a = *(const int *)pa, b = *(const int *)pb;
    return (a > b) - (a < b);
}

Prevent it by never subtracting to compare; always use explicit comparison.

Mistake 2: passing the wrong size to qsort

qsort(arr, n, sizeof arr, cmp);   /* WRONG: sizeof a pointer or whole array */

qsort needs the size of one element. Passing the array's total size or a pointer's size scrambles the data. Use sizeof arr[0] or sizeof *arr.

Mistake 3: confusing element count with byte count

size_t n = sizeof data;             /* WRONG: bytes, not element count */
size_t n = sizeof data / sizeof data[0];  /* CORRECT */

This only works on a real array in scope, not on a pointer — once an array decays to a pointer (e.g. inside a function), sizeof gives the pointer size, so pass n as a parameter.

Mistake 4: inner-loop off-by-one in a hand-written sort

Reading a[j] and a[j+1] with j going up to n instead of n - 1 reads one element past the end — a buffer over-read. Always double-check the upper bound of the inner loop.

Mistake 5: assuming qsort is stable

The C standard does not guarantee qsort keeps equal elements in their original order. If you need stability, sort by a composite key (add the original index as a tiebreaker) or use mergesort.

Debugging tips

Compiler errors

• "implicit declaration of function 'qsort'" — you forgot #include <stdlib.h>.
• "passing argument 4 ... from incompatible pointer type" — your comparator signature is wrong. It must be exactly int (*)(const void *, const void *).
• A warning about discarding const usually means you cast void * to int * instead of const int * inside the comparator.

Runtime / logic errors

• Output not sorted at all: check the size argument (sizeof *arr, not sizeof arr) and the element count.
• Sorted backwards: your comparator returns the wrong sign, or you used a - b and hit overflow. Swap the comparison or use (a > b) - (a < b).
• Crash / garbage values: likely an over-read past the array, or a comparator that dereferences the wrong type. Run under a sanitizer.

Concrete steps

1. Print the array before and after sorting to see what changed.
2. Compile with -Wall -Wextra and fix every warning.
3. Build with -fsanitize=address,undefined to catch out-of-bounds reads and overflow.
4. Add a temporary printf inside the comparator to see which pairs are compared and what you return.

Questions to ask when it does not work

• Am I passing the size of one element, or of the whole array?
• Does my comparator return negative / zero / positive for before / equal / after?
• Could any comparison overflow?
• Is my loop reading one element past the end?

Memory safety

Memory safety for sorting in C

• Bounds. Hand-written sorts touch a[j-1], a[j], and a[j+1]; one wrong bound is an out-of-bounds read or write (undefined behaviour). Keep inner loops within [0, n-1] and prove the bound on paper for small n.
• Element size vs. count. qsort trusts the size and nmemb you pass. A wrong size makes it read and write the wrong bytes, corrupting memory silently. Always use sizeof *arr for size and pass the real element count.
• Comparator correctness. The comparator must dereference the same type the array holds and must impose a consistent total order (if cmp(a,b) < 0 then cmp(b,a) > 0). An inconsistent comparator can make qsort read out of bounds — this is real undefined behaviour, not just a wrong result.
• Overflow. Comparing with subtraction (a - b) is signed overflow for extreme values, which is undefined. Use (a > b) - (a < b).
• Allocation lifetime. If you sort a heap-allocated array, check malloc for NULL and free it exactly once when done, as in the example.
• Initialization. Never sort an array whose elements were never assigned; reading uninitialized values is undefined behaviour and produces meaningless order.

Robust habit: compile with -Wall -Wextra -fsanitize=address,undefined while developing sorting code — most of these bugs surface immediately.

Real-world uses

Where sorting shows up

• Databases sort to satisfy ORDER BY, to build indexes, and to run merge joins. The standard libraries of essentially every language ship a tuned sort (often an O(n log n) hybrid).
• Operating systems and tooling: the Unix sort command, log merging, package dependency ordering.
• UI and web: leaderboards, sortable tables, ranked search results, "newest first" feeds.
• Embedded / systems: heapsort is popular where guaranteed O(n log n) and O(1) extra space matter and worst-case timing is required.

Professional best practices

Beginner rules

• Prefer the library sort (qsort in C) over hand-rolling one.
• Write comparators that return -1/0/1 via comparison, never subtraction.
• Use sizeof *arr for element size and pass the real count.
• Check malloc, and free what you allocate.

Advanced habits

• Pick the algorithm to fit the data: nearly-sorted -> insertion; need stability -> mergesort; need worst-case guarantees and tiny memory -> heapsort; general case -> the library's tuned quicksort/introsort.
• Make comparators total and transitive; add a tiebreaker key when you need stable results from an unstable sort.
• For very large data that does not fit in RAM, use external (merge-based) sorting.
• Benchmark before optimizing; the constant factors and cache behaviour often matter more than the asymptotic class for medium n.

Practice tasks

Practice

Beginner 1 — Verify sorted order

Write int is_sorted(const int *a, size_t n) that returns 1 if a is in non-decreasing order, else 0.

• Requirements: a single pass, no extra array, handle n == 0 and n == 1 (both sorted).
• Example: {1,2,2,5} -> 1; {1,3,2} -> 0.
• Hint: compare each pair a[i-1] and a[i]; return 0 on the first violation.
• Concepts: array traversal, loop bounds.

Beginner 2 — Descending qsort

Sort an int array into descending order using qsort.

• Requirements: write a comparator cmp_desc and call qsort with the correct size and count.
• Example: {5,1,3} -> 5 3 1.
• Hint: reverse the sign of the ascending comparator, e.g. (b > a) - (b < a).
• Concepts: qsort, comparator, overflow-safe comparison.

Intermediate 1 — Insertion sort with a swap counter

Implement insertion sort that also returns the number of element moves it performed.

• Requirements: size_t insertion_sort_count(int *a, size_t n); sort in place and return the count of shifts.
• Example: an already-sorted array should return 0.
• Hint: count each time you slide an element right.
• Concepts: insertion sort, in-place modification.

Intermediate 2 — Sort structs by two keys

Given struct Person { char name[32]; int age; };, sort an array by age ascending, breaking ties by name (use strcmp).

• Requirements: one comparator that first compares age, then falls back to strcmp(name).
• Example: two people aged 30 should appear in alphabetical name order.
• Hint: int d = (x->age > y->age) - (x->age < y->age); return d ? d : strcmp(x->name, y->name);
• Concepts: structs, qsort on non-int types, multi-key comparison, stability via tiebreaker.

Challenge — Merge two sorted arrays

Write int *merge_sorted(const int *a, size_t na, const int *b, size_t nb, size_t *out_len) that returns a newly allocated array containing all elements of a and b in sorted order, assuming a and b are each already sorted.

• Requirements: do it in O(na + nb) (the merge step of mergesort, no full re-sort); allocate the result, set *out_len, and let the caller free it; return NULL on allocation failure.
• Example: a={1,4,6}, b={2,3,5} -> {1,2,3,4,5,6}.
• Hint: walk two indices i and j, always copying the smaller front element.
• Concepts: the merge operation, malloc/free, bounds, linear-time merging.

Summary

Summary

• Sorting rearranges data into a defined order (ascending, descending, or by some key). A sort is stable if it keeps equal elements in their original relative order.
• Big-O compares algorithms by how work grows with n. Simple sorts (bubble, insertion) are O(n^2); merge, quick, and heap sort are O(n log n) — though quicksort's worst case is O(n^2).
• Trade-offs: mergesort is stable but uses O(n) extra space; quicksort is in place but unstable with a bad worst case; heapsort is in place and worst-case O(n log n) but unstable.
• Most important syntax: qsort(base, nmemb, size, compar) with a comparator that returns negative / zero / positive. Use sizeof *arr for size.
• Common mistakes: subtracting in the comparator (overflow), passing the wrong size or count, off-by-one inner loops, and assuming qsort is stable.
• Remember: for real C code, reach for qsort and write a correct, overflow-free comparator; reserve hand-written sorts for learning, tiny arrays, or nearly-sorted data.

Practice with these exercises

• Bubble sort
• Is it sorted?