Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Java

Quick sort

Explore the quick sort algorithm through its partitioning approach around a pivot element. Understand how this divide-and-conquer technique sorts arrays efficiently in place. Learn about its time and space complexities, advantages, limitations, and practical usage, helping you write optimized Java sorting solutions.

We'll cover the following...

Imagine a teacher asks students to line up around a chosen benchmark height. Everyone shorter than the benchmark stands on the left, everyone taller than the benchmark stands on the right, and then each side repeats the process with its own benchmark.

That is the core idea of quick sort. Instead of merging sorted halves like merge sort, quick sort repeatedly partitions the array around a pivot element.

Quick sort is a divide-and-conquer sorting algorithm that chooses a pivot, partitions the array so smaller elements go left, and larger elements go right, then recursively sorts the two partitions.

Why it is called “quick”: On average, quick sort produces balanced partitions and sorts efficiently with low constant overhead. That is why it performs well in practice.

How it works

Quick sort usually has three conceptual steps:

  • Choose a pivot.

  • Partition the array so values smaller than the pivot move left and values larger move right.

  • Recursively sort the left and right partitions.

The partition step is the heart of the algorithm. Once the pivot lands in its correct final position, it never needs to move again.

Important: The algorithm’s speed depends heavily on pivot choice. Good pivots create balanced partitions. Bad pivots create uneven partitions and can cause worst-case performance.

Interactive animation

This visualizer focuses on the partition idea. It highlights the pivot and shows how smaller and larger values conceptually separate around it.

Algorithm

Before writing Java, read through the algorithm and connect each step to the trace above.

  1. If the array has one element or is empty:

    1. It is already sorted, so return.

  2. Otherwise:

    1. Choose a pivot element (commonly the last element).

    2. Partition the array around the pivot:

      1. Initialize a pointer i to track the boundary of smaller elements.

      2. Traverse the array from left to right (excluding the pivot):

        1. For each element:

          1. If it is smaller ...