Sort

A sequence of elements \(\langle a_1, a_2, \ldots, a_n \rangle\) is considered sorted if its elements are such that \(\langle a_1 \le a_2 \le \ldots \le a_n \rangle\). A sorting algorithm is then defined as an algorithm that, given a sequence \(\langle a_1, a_2, \ldots, a_n \rangle\), produces a permutation \(\langle a'_1, a'_2, \ldots, a'_n \rangle\) such that \(\langle a'_1 \le a'_2 \le \ldots \le a'_n \rangle\).

See also

Sorting algorithms can sort arbitrary data using Comparators.

API

#include sort.h

Different algorithms and implementations for sorting a slice in place with the given comparator.

Functions

void sort_merge(struct slice *a, struct slice *w, int (*cmp)(void*, void*), size_t p, size_t r)

Sorts an array in place using the merge sort algorithm.

Given a slice containing an array a[p:r], write the sorted array to a[p:r]. The comparator receives pointers to the elements being compared. Uses an auxiliary slice as working memory. Data on the auxiliary slice will not be preserved.

Parameters:

  • a – Handle to the slice.

  • w – Handle to the auxiliary slice. Must have at least as much capacity as a. Must have the same element size as a.

  • cmp – Sort comparator.

  • p – Starting index of the array.

  • r – Ending index of the array.

Internals

Caution

Internals are documented for completeness and to make the codebase easier to understand. However, they should not be used directly.

void _merge(struct slice *a, struct slice *w, int (*cmp)(void*, void*), size_t p, size_t q, size_t r)

Merges two sorted arrays into one sorted array.

Given a slice containing two sorted arrays a[p:q] and a[q+1:r], merge them, and write the sorted result to a[p:r].

Uses an auxiliary slice as working memory. Data on the auxiliary slice will not be preserved.

This is an internal function that should not be used directly. You probably want sort_merge instead.

Parameters:

  • a – Handle to the slice.

  • w – Handle to the auxiliary slice. Must have at least as much capacity as a. Must have the same element size as a.

  • cmp – Function that compares two void pointers a and b, returning 1 if a <= b and 0 otherwise.

  • p – Starting index of the first array.

  • q – Ending index of the first array (the second array starts at q + 1).

  • r – Ending index of the second array.