The smallest free ID problem

freemin.awk

function swap(A, left, right, t) {
    t = A[left]
    A[left] = A[right]
    A[right] = t
}

function qsort(A, left, right, pivot, i, j) {
    if (left < right) {
        # select a pivot element
        pivot = left
        i = left
        j = right
        while (i < j) {
            # increment i till you get a number greater than the pivot element
            while (A[i] <= A[pivot] && i <= right)
                i++
            # decrement j till you get a number less than the pivot element
            while (A[j] > A[pivot] && j >= left)
               j--
            # if i < j swap the elements in locations i and j
            if (i < j) {
               swap(A, i, j)
            }
        }

        # when i >= j it means the j-th position is the correct position
        # of the pivot element, hence swap the pivot element with the
        # element in the j-th position
        swap(A, pivot, j)
        # Repeat quicksort for the two sub-arrays, one to the left of j
        # and one to the right of j
        qsort(A, left, j - 1)
        qsort(A, j + 1, right)
    }
}

function minfree(A) {
    n = length(A)

    qsort(A, 1, n)

    for (i = 1; i <= n; i++) {
        if (A[i+1] - A[i] != 1) {
            print A[i] + 1
            return
        }
    }

    print 0
}

BEGIN {
    split("18 4 8 9 16 1 14 7 19 3 0 5 2 11 6", A)
    minfree(A)
}