Description

This PR refactors the quick_sort function to use an in-place sorting approach, significantly improving space complexity and making it more aligned with standard quicksort implementations.

Problem

The current implementation:

• Creates new lists (lesser and greater) during partitioning using list comprehensions
• Uses collection.pop(pivot_index) to remove the pivot
• Returns a new sorted list instead of sorting in-place
• Has O(n) space complexity due to creating new lists at each recursion level

Solution

Refactored to use in-place sorting:

• Introduced a helper function _quick_sort(collection, low, high) that performs recursive in-place sorting
• Implemented _partition(collection, low, high) using the Lomuto partition scheme
• Uses in-place swapping instead of creating new lists
• The main quick_sort(collection) function now sorts the list in-place and returns it
• Still uses random pivot selection for better average-case performance

Benefits

• Space Complexity: Reduced from O(n) to O(log n) (only recursion stack)
• Memory Efficiency: No allocation of new lists during partitioning
• Performance: Better cache locality due to in-place operations
• Time Complexity: Maintains O(n log n) average case
• Standard Implementation: More aligned with canonical quicksort algorithms

Technical Details

The implementation uses the Lomuto partition scheme:

1. Randomly select a pivot and swap it with the last element
2. Maintain an index i that tracks the boundary of elements ≤ pivot
3. Iterate through the array, swapping smaller elements to the left partition
4. Place the pivot in its final position
5. Recursively sort left and right partitions

Describe your change:

• Fix a bug or typo in an existing algorithm? (Space complexity improvement)

Checklist:

• I have read CONTRIBUTING.md.
• This pull request is all my own work -- I have not plagiarized.
• I know that pull requests will not be merged if they fail the automated tests.
• This PR only changes one algorithm file.
• All functions have doctests that pass the automated testing.