Dual-Pivot Quicksort

dpquicksort.py

def swap(lst, i, j):
    if min(i,j) >= 0 and max(i,j) < len(lst) and i != j:
        lst[i], lst[j] = lst[j], lst[i]
        lst.log()

# This is Dual-Pivot Quicksort by Yaroslavskiy et al.
# Implemented following Sebastian Wild as in
#     https://www.uni-trier.de/fileadmin/fb4/prof/INF/TIN/Theorietag/TR.pdf
#     page 39
# Plus a bugfix: need to swap pivot candidates, otherwise swapping-in pivots in the end
# does not work.
def dpquicksort(lst, left=0, right=None):
    if right is None:
        right = len(lst) - 1
    
    if right - left >= 1:
        if lst[left] > lst[right]:
            swap(lst, left, right)            
        p = lst[left]
        q = lst[right]
        
        l = left + 1
        g = right - 1
        k = l        
        while k <= g:
            if lst[k] < p:
                swap(lst, k, l)
                l += 1
            elif lst[k] >= q:
                while lst[g] > q and k < g:
                    g -= 1
                swap(lst, k, g)
                g -= 1
                if lst[k] < p:
                    swap(lst, k, l)
                    l += 1
            k += 1
            
        l -= 1
        g += 1
        swap(lst, left, l)
        swap(lst, right, g)
        
        dpquicksort(lst, left, l-1)
        dpquicksort(lst, l+1, g-1)
        dpquicksort(lst, g+1, right)