Randomized Quick Sort

Divide and Conquer

Recursively breaks the problem into smaller sub-problems, solves them, and combines the results.

Probabilistic

Uses random choices to reduce the probability of worst-case performance.

In-Place

Requires a constant amount of extra memory space (O(1)), regardless of input size.

Unstable

Does not guarantee the relative order of elements with equal values.

Random pivot selection makes the expected split independent of input order. A Lomuto partition places the pivot and recursively sorts the two sides.

Visualize Fullscreen

Demo

20 elements • 4x Speed

No Data

Did you know?

Random pivot choice removes the fixed last-pivot worst-case pattern for already sorted input, though unlucky choices can still occur.
This implementation recurses into the smaller partition first, keeping recursion depth logarithmic even for lopsided splits.
The random pivot is moved to the end before a Lomuto partition, so the rest of the trace resembles ordinary Quick Sort. Two runs on identical data may choose different pivots and take different paths.

How it Works

Choose an index uniformly at random in the current range.
Move that value to the end and partition smaller values before it.
Recurse on both sides of the pivot.

Complexity Analysis

Best Case

O(n \log n)

Average

O(n \log n)

Worst Case

O(n^2)

Space

O(\log n)

Advantages

Expected O(n log n) comparisons on any fixed input.
In-place partitioning.

Disadvantages

Worst case remains quadratic.
Random choices make traces vary between runs.

Implementation

JavaScript randomized-quick-sort.js

function randomizedQuickSort(a) {
  function sort(lo, hi) {
    if (lo >= hi) return;
    const random = lo + Math.floor(Math.random() * (hi - lo + 1));
    [a[random], a[hi]] = [a[hi], a[random]];
    const pivot = a[hi]; let wall = lo;
    for (let i = lo; i < hi; i++)
      if (a[i] < pivot) [a[i], a[wall]] = [a[wall], a[i]], wall++;
    [a[wall], a[hi]] = [a[hi], a[wall]];
    sort(lo, wall - 1); sort(wall + 1, hi);
  }
  sort(0, a.length - 1); return a;
}