## quicksort()


Sort a list using the quicksort algorithm.


Usage


``` python
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.  <span style="font-weight: 600; color: #6c757d;">\[1\]</span> Hoare, C.A.R. (1961). "Algorithm 64: Quicksort." Communications of the ACM, 4(7), 321.
2.  <span style="font-weight: 600; color: #6c757d;">\[2\]</span> Cormen, T.H. et al. (2009). "Introduction to Algorithms", 3rd edition, MIT Press, Chapter 7.


## Examples

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

\[1, 1, 3, 4, 5, 9\]

``` python
>>> quicksort([])
```

\[\]