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

Quick sort

Explore the quick sort algorithm, a divide-and-conquer method that sorts arrays by choosing a pivot and recursively partitioning elements. Understand how pivot choice affects performance and learn the JavaScript implementation of this efficient in-place sorting technique.

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 JavaScript code, read through the algorithm and connect each step to the trace above.

  1. If the list 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 list around the pivot:

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

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

        1. For each element:

          1. If it is smaller than the pivot:

            1. Move the boundary forward.

            2. Swap the current element with the element at the boundary.

    3. After traversal:

      1. Place the pivot in its correct position by swapping it with the next boundary position.

    4. Recursively apply quick sort:

      1. Sort the left portion (elements ...