Function atimsort_

numpy/core/src/npysort/timsort.cpp:903–945

template <typename Tag>
static int
atimsort_(void *v, npy_intp *tosort, npy_intp num)
{
    using type = typename Tag::type;
    int ret;
    npy_intp l, n, stack_ptr, minrun;
    buffer_intp buffer;
    run stack[TIMSORT_STACK_SIZE];
    buffer.pw = NULL;
    buffer.size = 0;
    stack_ptr = 0;
    minrun = compute_min_run(num);

    for (l = 0; l < num;) {
        n = acount_run_<Tag>((type *)v, tosort, l, num, minrun);
        stack[stack_ptr].s = l;
        stack[stack_ptr].l = n;
        ++stack_ptr;
        ret = atry_collapse_<Tag>((type *)v, tosort, stack, &stack_ptr,
                                  &buffer);

        if (NPY_UNLIKELY(ret < 0)) {
            goto cleanup;
        }

        l += n;
    }

    ret = aforce_collapse_<Tag>((type *)v, tosort, stack, &stack_ptr, &buffer);

    if (NPY_UNLIKELY(ret < 0)) {
        goto cleanup;
    }

    ret = 0;
cleanup:

    if (buffer.pw != NULL) {
        free(buffer.pw);
    }

    return ret;
}

/* For string sorts and generic sort, element comparisons are very expensive,
 * and the time cost of insertion sort (involves N**2 comparison) clearly