Sorting Algorithms in C: Comparison and Choosing a Method

Sorting algorithms in C rearrange values into an order; searching algorithms locate a value. Start with insertion sort to learn movement through an array, merge sort when stable worst-case O(n log n) sorting matters, and heap sort when you need a worst-case bound with constant auxiliary storage. No single algorithm is always fastest for every workload.

Comparison table

The table describes the specific ordinary implementations linked below, sorting in ascending order. Time counts treat comparisons and element moves as constant-cost. Auxiliary space excludes the input array but includes recursion. Stability means equal keys retain their original relative order.

“Average” requires a model of input order or randomized choices; it is not a guarantee for one dataset. Quick sort's last-element pivot can repeatedly make unbalanced partitions on sorted, reverse-sorted or duplicate-heavy input. All listed O bounds are upper bounds, not universal exact operation counts.

Choose by the requirement

• Small or nearly sorted arrays: insertion sort is simple and does little shifting when there are few inversions.
• Teaching adjacent comparisons: bubble sort makes swaps easy to trace, but avoid using it as a large-data default.
• Few writes: selection sort makes few swaps while still doing quadratic comparisons; whether that helps depends on comparison and write costs.
• Stable ordering: insertion or merge sort can preserve equal records; plain integer tests alone do not demonstrate record identity.
• Bounded worst-case time and little extra memory: heap sort is a useful option, with no stability guarantee.
• General-purpose library use: C provides qsort, but its name is not a language guarantee that it uses quick sort.

Complete library-sort example

Use qsort from stdlib.h when its API and unspecified equal-key ordering fit your task. C17 does not specify its sorting algorithm, stability, auxiliary space or a complexity guarantee. The comparator returns a negative value, zero or a positive value. Do not return a - b for arbitrary integers: that subtraction can overflow. The relational form below returns only -1, 0 or 1.

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

static int compare_ints(const void *left, const void *right) {
    int a = *(const int *)left;
    int b = *(const int *)right;
    return (a > b) - (a < b);
}

int main(void) {
    int values[] = {64, 34, 25, 12, 22};
    size_t count = sizeof values / sizeof values[0];
    qsort(values, count, sizeof values[0], compare_ints);
    for (size_t i = 0; i < count; ++i) {
        printf("%s%d", i == 0 ? "" : " ", values[i]);
    }
    putchar('\n');
    return 0;
}

12 22 25 34 64

The pointer arguments identify elements of the original array. sizeof values[0] tells the library the size of each element. The comparator must impose a consistent ordering; changing the keys while comparing them or returning contradictory results violates that requirement. Sorting a structure by one field needs a comparator for that structure, not an unsafe cast to an unrelated type.

Learn with one input, then edge cases

For each linked algorithm, trace {64, 34, 25, 12, 22} and compare intermediate states, not only the shared final output 12 22 25 34 64. Then test empty input through a valid function call, one value, already sorted, reverse order, all equal, repeated negatives and integer extremes. A zero-length array declaration is not standard C.

For stable record sorts, add unique identities to equal keys and verify identity order separately. Benchmark optimized builds with realistic input distributions only after correctness checks; a single five-element timing is not evidence that one method is universally fastest.

Sorting is not searching

Linear search can inspect an unsorted array directly. Binary search requires a sorted array in the same order its comparisons assume. Sorting just to do one lookup may cost more than a single linear scan; sorting once can be worthwhile before many searches. Include preprocessing cost in comparisons.

Frequently asked questions

Does in-place mean stable?

No. Selection and heap sort can be in-place but unstable. Insertion sort is both in-place and stable in the linked strict-comparison implementation.

Does an O(n log n) algorithm always beat an O(n²) algorithm?

No. Input size, order, comparison cost and implementation overhead matter. Asymptotic growth is useful for scaling, not a substitute for measuring a real workload.

Are all these algorithms built into C?

No. The linked guides implement them explicitly. qsort is the standard-library sorting interface, with an implementation-chosen algorithm.

Use arrays, functions and the online compiler to try the complete programs. Each guide distinguishes its reference output from a live result.