In-place quicksort in python using recursion (a very simple implementation with easy-to-understand explanations)¶

There are many kinds of implementation of quicksort. The implementation in this article has the following features:

• Use recursion to make the code more readable.
• Sort in place. It has better performance than the merging new arrays way.
• Implement in a very simple way with few code lines and easy-to-understand variables.

Show me the code¶

Explanations are in the code comments:

def qsort(arr, start, end):
    # ignore one-item sub-array
    if start >= end:
        return
    # base_value will be compared by each value
    base_value = arr[end]
    # pivot_pos is a special index. from start to pivot_pos, values are smaller or equal to base_value
    pivot_pos = start - 1
    # traverse from start to end.
    for i in range(start, end + 1):
        if arr[i] <= base_value:
            # move smaller value, so that pivot_pos always point to a small value
            pivot_pos += 1
            arr[pivot_pos], arr[i] = arr[i], arr[pivot_pos]
    # in the last loop, pivot_pos points to base_value because arr[end] equals base_value
    # finally, values on the left of pivot_pos are smaller and values on the right are bigger
    qsort(arr, start, pivot_pos - 1)
    qsort(arr, pivot_pos + 1, end)

Test the code¶

example = [15, 12, 17, 21, 1, 9, 7]
qsort(example, 0, len(example) - 1)
print(example)  # output: [1, 7, 9, 12, 15, 17, 21]