Quick Sort

Definition

Quick sort is a recursive divide-and-conquer sorting algorithm that sorts a list by selecting a pivot element, partitioning the remaining elements into two sublists based on their comparison with the pivot, and then recursively sorting the sublists.

In simple words, quick sort:

picks a pivot,
places smaller elements on one side and larger elements on the other,
and repeats the same process on the smaller groups.

Formal idea

If an array is split around a pivot p, then:

all elements in the left partition are <= p,
all elements in the right partition are >= p,
and the pivot is in its final sorted position after partitioning.

Because it repeatedly divides the problem, quick sort is an example of a divide-and-conquer technique.

Main Content

1. First Concept: Divide and Conquer Strategy

Divide

The array is divided into two parts using a pivot element. This is done by rearranging elements so that those less than the pivot are placed on one side and those greater are placed on the other.

Conquer

Each partition is then sorted recursively using the same quick sort method until the subarrays become small enough to be trivially sorted.

Explanation

The divide-and-conquer strategy is the heart of quick sort. Unlike algorithms such as bubble sort, which compare adjacent elements repeatedly, quick sort reduces the problem size very quickly by splitting the array into smaller sections.

For example, consider the array:

[8, 3, 1, 7, 0, 10, 2]

If 8 is chosen as the pivot:

Left side: [3, 1, 7, 0, 2]
Pivot: 8
Right side: [10]

Then the left side is again partitioned, and the process continues recursively.

Why this concept matters

It makes quick sort efficient in many practical cases.
It demonstrates recursion clearly.
It reduces the amount of work needed compared to checking all elements repeatedly.

2. Second Concept: Pivot Selection and Partitioning

Pivot Selection

The pivot is the reference element used to divide the array into two parts. The choice of pivot affects performance.

Partitioning

This is the process of rearranging the array so that elements less than the pivot are on one side and elements greater than the pivot are on the other side.

Explanation

Partitioning is the most crucial operation in quick sort. A good partitioning method ensures that the pivot lands in its correct final position in the sorted array.

For example, using the array:

[9, 4, 7, 3, 10, 5]

Suppose 7 is chosen as pivot:

Elements smaller than 7: [4, 3, 5]
Pivot: [7]
Elements greater than 7: [9, 10]

After partitioning, the array may be arranged as:

[4, 3, 5, 7, 9, 10]

Now the pivot 7 is already in its final sorted position.

Common pivot choices

First element
Last element
Middle element
Random element
Median-of-three (median of first, middle, and last)

Why pivot selection matters

A poor pivot choice can lead to unbalanced partitions.
Balanced partitions reduce recursion depth and improve performance.
Random or median-based choices often give better practical performance.

3. Third Concept: Recursive Sorting and Performance Characteristics

Recursive Sorting

After partitioning, quick sort recursively sorts the left and right partitions until each partition contains zero or one element.

Performance Characteristics

Quick sort has different time complexities depending on the case, which makes it important to understand average, best, and worst-case behavior.

Explanation

After the pivot is placed in its correct position, quick sort does not need to touch it again. It then sorts the two smaller parts around it.

Example: [6, 2, 9, 1, 5]

If 5 is the pivot:

Left partition: [2, 1]
Pivot: 5
Right partition: [6, 9]

Then:

[2, 1] becomes [1, 2]
[6, 9] is already sorted

Final sorted array: [1, 2, 5, 6, 9]

Time complexity

Best case

O(n log n) Occurs when the pivot splits the array into nearly equal halves each time.

Average case

O(n log n) This is why quick sort is very efficient in real-world use.

Worst case

O(n^2) Happens when the pivot creates highly unbalanced partitions, such as when the array is already sorted and the first or last element is always chosen as pivot.

Space complexity

Usually O(log n) due to recursive call stack in balanced cases.
Can become O(n) in worst-case recursion depth.

Working / Process

1. Choose a pivot element

Select one element from the array as the pivot.
The pivot may be the first, last, middle, random, or median-of-three element.
The choice affects how balanced the partitions will be.

2. Partition the array

Rearrange the elements so that:
- values smaller than the pivot go to the left,
- values larger than the pivot go to the right.
The pivot is placed in its final sorted position.
This is the most important step because it reduces the sorting problem into smaller parts.

3. Recursively sort the subarrays

Apply quick sort to the left subarray and the right subarray.
Stop when a subarray has zero or one element, since it is already sorted.
The repeated partitioning and recursive calls eventually sort the complete array.

Example walkthrough

Take the array:

[10, 7, 8, 9, 1, 5]

Assume the last element 5 is the pivot.

First partition:

Smaller than 5: [1]
Pivot: 5
Greater than 5: [10, 7, 8, 9]

Array becomes: [1, 5, 10, 7, 8, 9]

Now sort the right side [10, 7, 8, 9].

If 9 is pivot:

Smaller than 9: [7, 8]
Pivot: 9
Greater than 9: [10]

Then:

[7, 8] becomes sorted as [7, 8]
[10] remains as is

Final sorted array: [1, 5, 7, 8, 9, 10]

ASCII visual illustration

Initial array: [10, 7, 8, 9, 1, 5]

After partition around 5:

[1]   [5]   [10, 7, 8, 9]

After sorting the right partition around 9:

[1]   [5]   [7, 8]   [9]   [10]

Final result:

[1, 5, 7, 8, 9, 10]

Advantages / Applications

Very fast on average

Quick sort is one of the fastest general-purpose sorting algorithms for large datasets.
Its average-case O(n log n) performance makes it highly efficient in practice.

Uses little extra memory

It can sort in place, meaning it does not require large additional arrays.
This makes it memory-efficient compared with some other divide-and-conquer sorts.

Widely used in real systems

Quick sort is used in libraries, programming language runtimes, and performance-critical software.
It is also useful as a conceptual model for understanding recursion, partitioning, and algorithm analysis.

Common applications

Sorting arrays and lists in programming
Preparing data for binary search and other searching operations
Internal sorting in libraries and systems
Large-scale data processing where average performance is important

Limitations to remember

Worst-case time complexity is O(n^2).
It is not a stable sorting algorithm in its standard form.
Its performance depends heavily on pivot selection and partition strategy.

Summary

Quick sort is a divide-and-conquer sorting algorithm that sorts by partitioning around a pivot.
It is very efficient in practice and usually runs in O(n log n) time.
Its main operations are pivot selection, partitioning, and recursive sorting.
Important terms to remember: pivot, partition, recursion, divide and conquer, stable sort, in-place sorting