Pragmatics of Sorting

Before diving into algorithms, there's a practical question to settle: in what order do we actually want things sorted? The answer is always application-specific.

Key Considerations

Increasing or Decreasing?

A set of keys is in ascending order when Sᵢ ≤ Sᵢ₊₁ for all 1 ≤ i < n, and descending order when Sᵢ ≥ Sᵢ₊₁. Different applications call for different directions — there is no universal default.

Key or Full Record?

Equal Keys?

Non-Numerical Data?

The Comparison Function

The clean solution to all of the above is to abstract ordering logic into a pairwise comparison function passed as an argument to your sort routine. It takes pointers to two elements a and b and returns:

• < 0 if a belongs before b

• > 0 if b belongs before a

• 0 if they are equal

Any reasonable language has a built-in sort routine. Use it — you are almost always better off than writing your own.

C

#include <stdlib.h>

/* Sort integers in increasing order */
int intcompare(int *i, int *j)
{
    if (*i > *j) return (1);
    if (*i < *j) return (-1);
    return (0);
}

/* Sort first n elements of array a */
qsort(a, n, sizeof(int), intcompare);

qsort sorts the first nel elements of the array at base, where each element is width bytes wide — making it generic across chars, ints, or arbitrary structs.

C++

Python