Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Quick Sort Algorithm

Last updated: 5 Oct 20269 min read
algorithm
MediumBy AITrove Editorial

Quick sort partitions a sequence around a pivot and recursively orders the lower and higher partitions. Its average work is O(n log n), while consistently uneven partitions can make it O(n²). This article uses three partitions so the duplicate-key rule is explicit. It is an algorithm applied to indexed storage, not a separate container.

Operational case

A dispatch board has shipment priorities 52, 47, and 61. It must display S-47, S-52, then S-61. The middle record supplies the first pivot; smaller records go left and larger records go right. Equal-priority records stay together in their input order in this particular implementation. A large already ordered feed may still create expensive partitions under a poor pivot rule, so a production system should measure the input shape and normally prefer the language's tested built-in sort for ordinary application code.

Working Python program

python
def quick_sort(records):
    if len(records) < 2:
        return records[:]
    pivot = records[len(records) // 2][0]
    lower = [record for record in records if record[0] < pivot]
    equal = [record for record in records if record[0] == pivot]
    higher = [record for record in records if record[0] > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

shipment_priority = [(52, "S-52"), (47, "S-47"), (61, "S-61")]
print(quick_sort(shipment_priority))

Output

Output
[(47, 'S-47'), (52, 'S-52'), (61, 'S-61')]

Time, space, and tradeoff

Each partition scans its current input. Balanced levels give O(n log n) time; a sequence of one-sided partitions gives O(n²) time and deep recursion. This version allocates new lists at every level, so it is easier to inspect but uses more memory than an in-place partition. The base case returns a copy rather than the caller's list, avoiding an alias surprise. Python's built-in stable sort is usually the safer application choice when the goal is simply ordered records; learning this implementation explains partition invariants and the worst-case boundary.

Common Mistakes

  • Do not call every pivot split balanced.
  • Do not claim this out-of-place version uses constant extra space.
  • Do not ignore the ordering requirement for equal-priority records.

Connected lessons

dsa
sorting
Storage details