quicksort()

Sort a list using the quicksort algorithm.

Usage

quicksort(arr)

Implements the classic quicksort algorithm with Lomuto partition scheme. Returns a new sorted list without modifying the original.

Parameters

arr: list

A list of comparable elements to sort.

Returns

list

A new list containing the same elements in sorted order.

Notes

The average-case time complexity is O(n log n), but the worst case is O(n^2) when the pivot selection is poor (e.g., already sorted input with first-element pivot).

This implementation uses the last element as the pivot and creates new lists for the partitions, so it is not in-place.

References

1. Hoare, C.A.R. (1961). “Algorithm 64: Quicksort.” Communications of the ACM, 4(7), 321.
2. Cormen, T.H. et al. (2009). “Introduction to Algorithms”, 3rd edition, MIT Press, Chapter 7.

Examples

>>> quicksort([3, 1, 4, 1, 5, 9])
[1, 1, 3, 4, 5, 9]

>>> quicksort([])
[]