quicksort

For inplace, the pivot is first moved to the end, the rest of the array is partitioned, and the pivot is moved to the correct index. The original order of duplicates is NOT maintained.

// space: O(1), inplace
void quicksort(int[] array, int start, int end):
    if start >= end:
        return
    pivot, pivotindex = partition(a, start, end)
    // sort partitions
    quicksort(array, start, pivotindex - 1)
    quicksort(array, pivotindex + 1, end)

(pivot, pivotindex) partition(a, start, end):
    pivotindex = random.next(start, end) // start, end inclusive
    pivot = array[pivotindex]
    // move pivot to end
    swap(array, pivotindex, end)
    // partition array
    lo = start
    hi = end - 1
    while lo <= hi:
        if array[lo] <= pivot:
            lo++
        else:
            swap(array, hi, lo)
            hi--
    pivotindex = lo // lo is pivot's index = hi +1
    // move pivot to correct index
    swap(array, pivotindex, end)
    return (pivot, pivotindex)


// space: O(n), not inplace
void quicksort_notinplace(int[] array, int start, int end)
    if start >= end : 
        return
    pivot = start // or random
    pivotvalue = array[pivot]
    copy = new int[end - start + 1]
    lo = 0
    hi = copy.Length - 1
    pivotindex = lo
    for (int i = start; i <= end; i++) :
        if i == pivot :
            continue
        if array[i] < pivotvalue : 
            copy[lo] = array[i]
            lo++
            pivotindex++
        else : 
            copy[hi] = array[i]
            hi--
    // at this point: lo = hi, lo = pivotindex
    copy[pivotindex] = pivotvalue
    Array.Copy(copy, 0, array, start, copy.Length)
    // sort partitions
    quicksort(array, start, start + lo - 1)
    quicksort(array, start + lo + 1, end)

Time: O(n²) worst case, O(nlogn) on average. Random pivot is better than picking start or end as pivot to sort asc/desc values. Array with same values incurs worst case.