Quick sort is a fast sorting algorithm that uses a “divide-and-conquer” strategy to arrange elements (like numbers) in order.

Quick Scoop: What Is Quick Sort?

At a high level, quick sort works by repeatedly splitting the array around a special element called a pivot. Elements smaller than the pivot go to its left, and elements larger go to its right; then the same process is applied to the left and right parts until everything is sorted.

Intuition: Imagine you pick one card from a messy pile as a reference card, move all smaller cards to its left and all bigger ones to its right, then repeat this inside each side until the pile is perfectly ordered.

How Quick Sort Works (Step-by-Step)

  1. Choose a pivot
    • Pick one element from the array (often first, last, middle, or a random element).
  1. Partition around the pivot
    • Rearrange the array so that:
      • All elements less than the pivot come before it.
      • All elements greater than the pivot come after it.
      • The pivot ends up in its final sorted position.
  1. Recursively sort subarrays
    • Recursively apply steps 1–2 to:
      • The left subarray (elements less than pivot).
      • The right subarray (elements greater than pivot).
  1. Stop condition
    • When a subarray has size 0 or 1, it is already sorted, and recursion stops.

A very compact pseudo-code view:

  • If the array has 0 or 1 element, return.
  • Partition array around pivot so left < pivot < right.
  • Quick sort left part, quick sort right part.

Mini Example

Take the array: $$$$.

  • Pick pivot = 5.
  • Partition: move smaller elements left, larger right → $$$$; 5 is now in its final position.
  • Recursively sort →becomes→becomes→becomes.
  • Recursively sort $$$$ → already sorted.
  • Final result: $$$$.

Why Quick Sort Is Popular

  • Fast on average
    • Average and best time complexity: O(nlog⁡n)O(n\log n)O(nlogn).
* Often faster in practice than many other comparison-based sorts like merge sort or heap sort on large random data.
  • In-place
    • Can be implemented to use only O(log⁡n)O(\log n)O(logn) extra space (mainly for recursion), so it does not need large extra arrays.
  • Widely used in libraries
    • Variants of quick sort (or hybrid algorithms using quick sort) are used in standard library sorting functions such as C++ std::sort and Java Arrays.sort for primitive types.

Performance at a Glance (HTML Table)

[3][7] [3][7] [1][7] [7][3]
Case Time Complexity Notes
Best O(n log n) Balanced partitions; pivot splits array roughly in half each time.
Average O(n log n) Typical behavior on random data; reason it’s considered very efficient.
Worst O(n²) Happens if pivots are consistently bad (e.g., always smallest or largest element in already sorted data).
Space O(log n) Recursive stack space when implemented in-place.

A Few Extra Properties

  • Quick sort is a comparison sort: it only uses element comparisons to decide order.
  • Most straightforward implementations are not stable, meaning equal elements might not keep their original relative order.
  • There are many practical tweaks (randomized pivot, three-way partitioning) that improve behavior on real-world data.

TL;DR : Quick sort is a divide-and-conquer sorting algorithm that picks a pivot, partitions the array into “less than pivot” and “greater than pivot,” and recursively sorts those parts, giving O(nlog⁡n)O(n\log n)O(nlogn) performance on average with low extra memory.

Information gathered from public forums or data available on the internet and portrayed here.