Cython: QuickSort code

• cimport: This directive is used to import a Cython-level version of the numpy module.
• ctypedef: This directive is used to define a Cython type alias for numpy.int_t.
• cdef: This directive is used to define a Cython function or variable. Cython functions and variables are compiled to C and are not accessible from Python.
• nogil: This decorator is used to indicate that a Cython function does not need to acquire the Global Interpreter Lock (GIL), which allows it to be executed concurrently with other Cython functions that also do not need the GIL. This can be useful for improving the performance of parallel code.
• cython.boundscheck, cython.wraparound, cython.initializedcheck, and cython.binding: These directives are used to disable bounds checking, negative index wrapping, uninitialized memory access checking, and name binding for faster execution. These directives should be used with caution, as they can result in undefined behavior if the code is not written correctly.

 

import numpy as np
cimport numpy as np

import cython

DEF CUTOFF = 32

ctypedef np.int_t stype

def sort(stype[:] a):
    qsort(a, 0, len(a))

@cython.boundscheck(False)
@cython.wraparound(False)
@cython.initializedcheck(False)
@cython.binding(False)
cdef void qsort(stype[:] a, Py_ssize_t start, Py_ssize_t end) nogil:
    if (end - start) < CUTOFF:
        insertion_sort(a, start, end)
        return
    cdef Py_ssize_t boundary = partition(a, start, end)
    qsort(a, start, boundary)
    qsort(a, boundary+1, end)

@cython.boundscheck(False)
@cython.wraparound(False)
@cython.initializedcheck(False)
@cython.binding(False)
cdef Py_ssize_t partition(stype[:] a, Py_ssize_t start, Py_ssize_t end) nogil:
    # assert end > start
    cdef:
        Py_ssize_t i = start, j = end-1
        stype pivot = a[j]
    while True:
        # assert all(x < pivot for x in a[start:i])
        # assert all(x >= pivot for x in a[j:end])

        while a[i] < pivot:
            i += 1
        while i < j and pivot <= a[j]:
            j -= 1
        if i >= j:
            break
        # assert a[j] < pivot <= a[i]
        swap(a, i, j)
        # assert a[i] < pivot <= a[j]
    # assert i >= j and i < end
    swap(a, i, end-1)
    # assert a[i] == pivot
    # assert all(x < pivot for x in a[start:i])
    # assert all(x >= pivot for x in a[i:end])
    return i

cdef inline void swap(stype[:] a, Py_ssize_t i, Py_ssize_t j) nogil:
    a[i], a[j] = a[j], a[i]

@cython.boundscheck(False)
@cython.wraparound(False)
@cython.initializedcheck(False)
@cython.binding(False)
cdef void insertion_sort(stype[:] a, Py_ssize_t start, Py_ssize_t end) nogil:
    cdef:
        Py_ssize_t i, j
        stype v
    for i in range(start, end):
        #invariant: [start:i) is sorted
        v = a[i]; j = i-1
        while j >= start:
            if a[j] <= v: break
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v