Quick Sort

DSA · Sorting Algorithms

Theory

Quick sort picks a pivot, partitions the array so smaller elements go left and larger go right, then recursively sorts both sides. With good pivots each partition splits the work roughly in half, giving O(n log n) average time. A bad pivot (for example always the smallest element) gives O(n²), which random or median-of-three pivots avoid. The in-place version uses only O(log n) stack space.

Why we use it

It is usually the fastest general-purpose comparison sort in practice because of its cache-friendly in-place partitioning.

When to use it

Use it for large in-memory arrays when stability is not required. Quickselect, its cousin, finds the kth smallest element in O(n) average.

How it works

  1. quickSort(arr, low, high)
  2. low < high? Yes: Choose a pivot. No: Return (0 or 1 element).
  3. Partition: smaller left of pivot, larger right
  4. Pivot is now in its final position p
  5. quickSort(low, p-1) and quickSort(p+1, high)
  6. Done

Syntax

quick_sort(arr, lo, hi):
    if lo < hi:
        p = partition(arr, lo, hi)
        quick_sort(arr, lo, p-1)
        quick_sort(arr, p+1, hi)

Time: O(n log n) avg, O(n²) worst   Space: O(log n)   Not stable

Example

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

def quick_sort(arr, lo, hi):
    if lo < hi:
        p = partition(arr, lo, hi)
        quick_sort(arr, lo, p - 1)
        quick_sort(arr, p + 1, hi)
    return arr

data = [10, 7, 8, 9, 1, 5]
print(quick_sort(data, 0, len(data) - 1))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic