Skip to content

feat: implement quicksort algorithm

Yun.Long requested to merge wip/implement-quicksort into main

Summary

This MR adds a complete implementation of the quicksort algorithm with two different approaches:

Implementations

  1. quicksort() - Recursive implementation using list comprehensions

    • Returns a new sorted list
    • Simple and easy to understand
    • Uses pivot selection from middle element
  2. quicksort_inplace() - In-place implementation using Lomuto partition scheme

    • Sorts the list in-place
    • More memory efficient (O(log n) space)
    • Uses last element as pivot

Features

  • Both implementations handle all edge cases (empty list, single element, etc.)
  • Comprehensive test suite with 13 test cases
  • All tests pass successfully
  • Both implementations produce identical results
  • Well-documented code with docstrings

Test Coverage

  • Empty list
  • Single element list
  • Already sorted list
  • Reverse sorted list
  • Random list
  • List with duplicate elements
  • Consistency between both implementations

Performance

  • Time complexity: O(n log n) average, O(n²) worst-case
  • Space complexity: O(n) for quicksort(), O(log n) for quicksort_inplace()

This implementation is ready for production use and follows best practices for algorithm implementation.

Merge request reports