Polymorphic Sorting in C Using the qsort Function

The C standard library provides the qsort function to sort arbitrary arrays regardless of their underlying data type. This article explains how qsort achieves runtime polymorphism in a statically typed language without templates or generics, utilizing generic pointers (void *), explicit element size offsets, and user-defined comparison function pointers to decouple sorting logic from data representation.

The qsort Function Signature

The prototype for qsort, defined in <stdlib.h>, is:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

The function accepts four parameters:

  1. base: A pointer to the first element of the array.
  2. nmemb: The number of elements in the array.
  3. size: The size in bytes of each individual element.
  4. compar: A pointer to a comparison function.

Type Erasure with void *

C does not feature built-in generics or class inheritance. To achieve polymorphism, qsort erases type information by accepting the array target as a generic void *. Because the compiler cannot know the concrete type of the array items at compile time, the implementation cannot use standard array indexing or direct pointer arithmetic (e.g., base[i]).

Memory Traversal via Byte Offsets

To traverse an array of unknown types, qsort relies on the size argument. Internally, the function casts base to a byte-addressable pointer, typically char * or unsigned char *.

To locate the \(i\)-th element, qsort calculates its memory offset using the formula:

\[\text{Address of element } i = (\text{char } *)\text{base} + (i \times \text{size})\]

This allows the sorting algorithm to navigate between elements, partition subarrays, and pass pointers to individual elements without knowing their underlying concrete types.

Delegating Logic Through Function Pointers

While qsort can manage memory layout and element rearrangement, it cannot inherently evaluate whether one arbitrary block of bytes is "greater than" or "less than" another. It delegates this domain-specific logic to the caller via a function pointer:

int (*compar)(const void *, const void *)

The Comparison Protocol

The comparison function must conform to a standardized contract:

  • Return an integer less than 0 if the first argument is considered smaller than the second.
  • Return 0 if the two arguments are considered equal.
  • Return an integer greater than 0 if the first argument is considered greater than the second.

Inside the comparator, the developer casts the incoming const void * arguments back to the appropriate concrete type to perform the comparison.

Implementation Example

The following example demonstrates sorting a custom structure using a specialized comparator:

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

typedef struct {
    char name[32];
    int score;
} Player;

int compare_players_by_score(const void *a, const void *b) {
    const Player *player_a = (const Player *)a;
    const Player *player_b = (const Player *)b;

    // Sort descending by score
    return player_b->score - player_a->score;
}

int main(void) {
    Player team[] = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78}
    };
    size_t count = sizeof(team) / sizeof(team[0]);

    qsort(team, count, sizeof(Player), compare_players_by_score);

    for (size_t i = 0; i < count; i++) {
        printf("%s: %d\n", team[i].name, team[i].score);
    }

    return 0;
}

Generic Data Swapping

When the comparator indicates that elements are out of order, qsort must swap them. Because it does not know the type, it cannot use an assignment operator (=). Instead, it swaps elements byte-by-byte—either by copying memory blocks using a temporary buffer allocation, or via word-sized chunk swaps until size bytes have been exchanged.

Summary

The polymorphism of qsort relies on a clean separation of concerns:

  • qsort handles structure and movement: It manages the overarching sorting algorithm, memory indexing, and swapping using byte offsets and size.
  • The caller handles semantics: The caller defines data interpretation and ordering via a function pointer that evaluates two const void * memory locations.