Implementing Recursive Quicksort

For this implementation, inputs are finite integers with their ordinary total order. Pick the first value as pivot. Build a lower list containing values less than it, an equal list containing every value equal to it, and an upper list containing values greater than it. Recursively sort lower and upper, then concatenate the three results.

Every original item must belong to exactly one partition. This excludes values with unusual comparison behaviour, such as a floating NaN for which less-than, greater-than and equality comparisons can all be false. The equal partition is not merely a single copied pivot: it retains all repeated pivot values, preventing silent data loss and avoiding recursion on an all-equal partition.

For [4,1,4,3], pivot 4 produces lower [1,3], equal [4,4] and upper []. Sorting [1,3] chooses pivot 1, with upper [3]. Empty and singleton inputs return a copy immediately. Since at least the pivot is removed into equal for each nontrivial call, the recursive lower/upper inputs are smaller.

The source list remains unchanged because this implementation constructs new lists rather than swapping source elements. That makes it easy to trace but does not make it an in-place quicksort. A different partition procedure can work within one array using index bounds; its traces, memory use and tie handling need their own explanation. Do not mix one version’s code with another version’s claimed properties.

With well-balanced partitions, recursion has approximately log n levels and partition work totals O(n) at each level, giving O(n log n) work. With the first pivot and already sorted distinct input, one child has n−1 items repeatedly, leading to quadratic work and linear recursion depth. A large input can hit Python’s recursion limit before a theoretically terminating computation finishes.

Three-way equality grouping handles all-equal input efficiently in this version, but does not remove every bad pivot case. Creating and retaining lists uses additional memory, especially along unbalanced recursion; never label it O(1) auxiliary space. Compare complete behaviour on empty, duplicate, sorted, reverse and mixed-sign inputs. Use Python’s trusted sorted result as a test oracle rather than testing a sort with another copy of the same partition code.

def quick_sort(values):
    if len(values) <= 1:
        return values[:]
    pivot = values[0]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    upper = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(upper)

original = [4, 1, 4, 3]
print(quick_sort(original))
print(original)

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.