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

Quick sort

Explore how quick sort uses a pivot to partition and recursively sort elements efficiently. Understand its average and worst-case performance, in-place nature, and when to apply it for optimized sorting in Go.

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

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

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

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

        1. For each element:

          1. If it is smaller than ...