#ifndef _AL_ARRAY_SORT_H
#define _AL_ARRAY_SORT_H

#include "lib.h"

/* https://en.wikipedia.org/wiki/Insertion_sort
i ← 1
while i < length(A)
    x ← A[i]
    j ← i
    while j > 0 and A[j-1] > x
        A[j] ← A[j-1]
        j ← j - 1
    end while
    A[j] ← x
    i ← i + 1
end while
*/

#define AL_INSERSION_SORT(data, type, count, cmp)      \
    do {                                               \
        u32 i = 1, k;                                  \
        type x;                                        \
        while (i < count) {                            \
            k = i;                                     \
            x = (data)[i];                             \
            while (k > 0 && cmp(&(data)[k - 1], &x) > 0) { \
                (data)[k] = (data)[k - 1];             \
                k--;                                   \
            }                                          \
            (data)[k] = x;                             \
            i++;                                       \
        }                                              \
    } while (0)

#ifdef AL_USE_STDLIB
#define AL_STDLIB_QSORT(data, type, count, cmp) qsort(data, (size_t)count, sizeof(type), cmp)
#endif

#endif // _AL_ARRAY_SORT_H