Quick Sort

sorting

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Picks a pivot element and partitions the array around it, recursively sorting the partitions.

Time Complexity

Best

\mathrm{O}\left(n \log n\right)

Avg

\mathrm{O}\left(n \log n\right)

Worst

\mathrm{O}\left(n^{2}\right)

Max Operations

Worst-case bound

\frac{n(n-1)}{2}

Used for efficiency calculation in Stats Panel

Space Complexity

Aux

\mathrm{O}\left(\log n\right)

Recursive call stack depth (avg log n, worst n)

Pseudocode

1procedure quickSort(A, lo, hi)

2pivot = A[lo]

3move i right while A[i] < pivot

4move j left while A[j] > pivot

5if i < j: swap(A[i], A[j])

6swap(A[lo], A[j])

7quickSort(A, lo, j-1)

8quickSort(A, j+1, hi)