partition.c

/* Modified slightly from https://github.com/naftaliharris/lazysort */
int partition(LSObject *ls, int left, int right) {
    PyObject **ob_item = ls->xs->ob_item;  /* The array to be sorted */
    int piv_idx = pick_pivot(ls, left, right);
    PyObject *pivot = ob_item[piv_idx];

    SWAP(left, piv_idx);
    int last_less = left;

    /* Invariant: last_less and everything to its left is less than
     * pivot or the pivot itself */

    for (int i = left + 1; i < right; i++) {
        __builtin_prefetch(ob_item[i+3]);  /* This is the added line */
        IF_LESS_THAN(ob_item[i], pivot) {
            last_less++;
            SWAP(i, last_less);
        }
    }

    SWAP(left, last_less);
    return last_less;
}