Names specified here
Name	Description			Source	Availability
`bsearch()`	Search array		(·)	`<stdlib.h>`	C89	C90	C95	C99	C11
`bsearch_s()`	Search array	?	(·)	`<stdlib.h>`					C11
`qsort()`	Sort array		(·)	`<stdlib.h>`	C89	C90	C95	C99	C11
`qsort_s()`	Sort array	?	(·)	`<stdlib.h>`					C11

The standard library supports the sorting of arrays on any criteria, and searching an array sorted on any criteria. As an example, we will define a structure to represent a person, and an array of such structures with the data already filled in:

struct person {
  char gn[30]; // given name
  char sn[30]; // surname
  time_t dob; // date of birth
  long long credit;
};

struct person database[] = {
  ...
};
#define ENTRY_COUNT (sizeof database / sizeof database[0])

We can define an ordering for these structures, primarily sorting on surname, then given name if surnames are identical, then date of birth if given names are also identical:

int compare_persons(const struct person *p1,
                    const struct person *p2)
{
  {
    int rc = strcmp(p1->sn, p2->sn);
    if (rc != 0) return rc;
  }

  {
    int rc = strcmp(p1->gn, p2->gn);
    if (rc != 0) return rc;
  }

  return copysign(1.0, difftime(p1->dob, p2->dob));
}

Note that we specify it to return negative if *p1 should be ordered earlier than *p2, positive if later, and zero if there is no ordering. Note also that we are not interested in ordering according to credit.

Sorting arrays

We can sort an array like the one above using either of these functions:

#include <stdlib.h>
void qsort(void *base,
           size_t nmemb,
           size_t size,
           int (*cmp)(const void *elem1,
                      const void *elem2));

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdlib.h>
errno_t qsort_s(void *base,
                rsize_t nmemb,
                rsize_t size,
                int (*cmp)(const void *elem1,
                           const void *elem2,
                           void *ctxt),
                void *ctxt);

Both take the start of an array base, the number of elements in the array nmemb, the size of each element in the array size, and a pointer to a comparison function cmp. Like our compare_persons function, the comparison function is expected to take two pointers elem1 and elem2, and yield positive, negative or zero according to their relative ordering. Because of the differing parameter types, we cannot pass a pointer to compare_persons directly to these functions without rewriting it. An alternative is to write a wrapper with the correct types:

static int cmpper_for_qsort(const void *elem1,
                            const void *elem2)
{
  return compare_persons(elem1, elem2);
}

qsort(database,
      ENTRY_COUNT,
      sizeof database[0],
      &cmpper_for_qsort);

The wrapper for qsort_s is similar:

static int cmpper_for_qsort_s(const void *elem1,
                              const void *elem2,
                              void *ctxt)
{
  return compare_persons(elem1, elem2);
}

qsort_s(database,
        ENTRY_COUNT,
        sizeof database[0],
        &cmpper_for_qsort_s,
        NULL);

The comparison function will only be invoked with elem1 and elem2 pointing to elements of the specified array. The final argument to qsort_s is passed unmodified as the third argument ctxt in every call to the comparison function, allowing user-defined context to be passed through without using static storage. In summary, we inject the behaviour defined by our comparison function into the sorting algorithm that qsort and qsort_s implement. Despite the name, there is no reason to believe that the algorithm is Quick Sort; the function may use any algorithm, and may even choose different algorithms based on, for example, the size of the array, the size of elements, etc.

qsort_s returns non-zero if nmemb or size exceed RSIZE_MAX.

The sorting functions re-arrange elements by copying them byte-by-byte, which is possible because the size of each element is provided. To reduce copying, it might be appropriate to have a separate array of pointers to the structures, and sort the pointers:

const struct person *ptrs[ENTRY_COUNT] = {
  &database[0],
  &database[1],
  &database[2],
  ...
};

static int cmpper_for_qsort(const void *elem1,
                            const void *elem2)
{
  const struct person *const *pp1 = elem1;
  const struct person *const *pp2 = elem2;
  return compare_persons(*pp1, *pp2);
}

qsort(ptrs,
      ENTRY_COUNT,
      sizeof ptrs[0],
      &cmpper_for_qsort);

This technique is also appropriate if you want to build multiple indices to the same array, or an index to something that isn't an array.

Searching ordered arrays

Searching through an ordered array is done with a comparison function, passed to one of these functions:

#include <stdlib.h>
void *bsearch(const void *base,
              const void *base,
              size_t nmemb,
              size_t size,
              int (*cmp)(const void *key,
                         const void *elem));

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdlib.h>
void *bsearch_s(void *base,
                rsize_t nmemb,
                rsize_t size,
                int (*cmp)(const void *key,
                           const void *elem,
                           void *ctxt),
                void *ctxt);

They take the start of an array base, the number of elements in the array nmemb, the size of each element in the array size, and a pointer to a comparison function cmp. They also take an initial argument key which identifies what to search for. It is always passed as the first argument to the comparison function, which these functions use to compare it with any elements of the array as it sees fit, probably according to a binary search. The comparison function should therefore be congruent to one that was or could have been used to order the array. Like qsort_s, bsearch_s takes an additional argument ctxt of type void *, which is passed as the third argument to its comparison function.

The key doesn't have to be of the same type as the array elements. We could reasonably re-use struct person as the key type, re-use the same comparison function that we used to sort the array, and fill in only the fields that the comparison function checks. However, let's demonstrate the use of a separate key type:

struct person_key {
  char gn[30]; // given name
  char sn[30]; // surname
  time_t dob; // date of birth
};

int compare_person_key(const struct person_key *key,
                       const struct person *elem)
{
  {
    int rc = strcmp(key->sn, elem->sn);
    if (rc != 0) return rc;
  }

  {
    int rc = strcmp(key->gn, elem->gn);
    if (rc != 0) return rc;
  }

  return copysign(1.0, difftime(key->dob, elem->dob));
}

This function is not type-compatible with what bsearch and bsearch_s want, so we have to either re-write or wrap them:

static int cmpper_for_bsearch(const void *key,
                              const void *elem)
{
  return compare_person_key(key, elem);
}

static int cmpper_for_bsearch_s(const void *key,
                                const void *elem,
                                void *ctxt)
{
  return compare_person_key(key, elem);
}

struct person_key key = {
  "Fred",
  "Bloggs",
  FREDS_DOB
};

struct person *res = bsearch(&key,
                             database,
                             ENTRY_COUNT,
                             sizeof database[0],
                             &cmpper_for_bsearch);

struct person *res = bsearch_s(&key,
                               database,
                               ENTRY_COUNT,
                               sizeof database[0],
                               &cmpper_for_bsearch_s,
                               NULL);

bsearch and bsearch_s return a pointer to a matching element, or NULL if they failed to find a match. bsearch_s also returns NULL if nmemb or size exceed RSIZE_MAX.