Sorting is a fundamental problem in computer science. Each method of sorting has trade-offs in time and space complexity. Sorting is often the first step in solving more complex problems.

Sorting Functions

Most of the time we don’t care about any of this theoretical stuff. We just want the damn thing sorted! Most languages include some sort of sorting, either through their standard libraries, or as method on a fundamental data type.

C has the qsort sorting function in its standard library. Despite its name it is not necessarily quick sort. The implementation is vendor specific. qsort requires 4 parameters:

#include <stdlib.h>

/* basic integer comparator function */
int cmp(const void* elem1, const void* elem2) {
    int *x = (int *) elem1;
    int *y = (int *) elem2;
    return *x - *y;

qsort(array, array_length, sizeof(int), cmp);


Sorting Implementations

Methods of sorting include:

Implementations of sorting algorithms can be tricky. Why?


The sorting algorithms in many languages take a comparator functions as parameter. Comparators themselves take two parameters, a and b, and returns:

When sorting numbers in ascending order you could simply return b-a

One trick with comparators is to sort on a secondary value when when the primary values are equal.