Sorting Algorithms

📋 Quick Reference

Algorithm	Time (Best)	Time (Avg)	Time (Worst)	Space	Stable
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No

One-liner: Sorting arranges elements in order; choose algorithm based on data size, memory constraints, and stability needs.

🎮 Interactive Visualizer

Watch different sorting algorithms race side-by-side:

QuickSort
Time: O(n log n)Space: O(log n)Comparisons: 0Swaps: 0
1 / 0
✓ Use when:General purpose, cache-friendly, average O(n log n) with low constant factor
✗ Avoid when:Already sorted data without randomization, many duplicate keys
Pseudocode
1quickSort(arr, low, high):
2  if (low < high)
3    pivot = partition(arr, low, high)
4    quickSort(arr, low, pivot-1)
5    quickSort(arr, pivot+1, high)
6 
7partition(arr, low, high):
8  pivot = arr[high]
9  i = low - 1
10  for (j = low; j < high; j++)
11    if (arr[j] <= pivot)
12      i++; swap(arr[i], arr[j])
13  swap(arr[i+1], arr[high])
14  return i + 1
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Size15
Default
Default
Comparing
Comparing
Swapping
Swapping
Pivot
Pivot
Sorted
Sorted
P · [ ] · R
Loading visualizer...

Try these:

Switch between algorithms using the selector
Compare how many swaps/comparisons each makes
Notice which algorithms are faster on nearly-sorted data

Side-by-Side Comparison

Algorithm Comparison
Race Mode
Array: []
VS
Bubble Sort
Pseudocode
1for (i = 0; i < n-1; i++)
2  for (j = 0; j < n-i-1; j++)
3    if (arr[j] > arr[j+1])
4      swap(arr[j], arr[j+1])
Variables
—
QuickSort
Pseudocode
1quickSort(arr, low, high)
2  if (low < high)
3    pi = partition(arr, low, high)
4    quickSort(arr, low, pi-1)
5    quickSort(arr, pi+1, high)
Variables
—
Size8
Speed
Loading visualizer...

🔧 Algorithm Implementations

Bubble Sort

JAVA(14 lines)
Code
Loading syntax highlighter...

Selection Sort

JAVA(13 lines)
Code
Loading syntax highlighter...

Insertion Sort

JAVA(12 lines)
Code
Loading syntax highlighter...

Merge Sort

JAVA(27 lines)
Code
Loading syntax highlighter...

Quick Sort

JAVA(23 lines)
Code
Loading syntax highlighter...

Java Standard Library

JAVA(16 lines)
Code
Loading syntax highlighter...

📊 When to Use Which Algorithm

Small Arrays (n < 50)

Use: Insertion Sort

Simple, low overhead
Very fast for small n
Java's Arrays.sort uses it for small subarrays

General Purpose

Use: Quick Sort (primitives) or Merge Sort/TimSort (objects)

Quick Sort: Fastest in practice for primitives
Merge Sort: Stable, guaranteed O(n log n)
TimSort: Hybrid, exploits existing order

Memory Constrained

Use: Heap Sort or Quick Sort

Both use O(1) or O(log n) extra space
Heap Sort is guaranteed O(n log n)

Nearly Sorted Data

Use: Insertion Sort or TimSort

O(n) for nearly sorted data
TimSort specifically designed for this

Stability Required

Use: Merge Sort or TimSort

Maintains relative order of equal elements
Critical for multi-key sorting

🧩 Stability Explained

Stable sort: Equal elements maintain their relative order

JAVA(10 lines)
Code
Loading syntax highlighter...

⚠️ Common Pitfalls

1. Wrong Algorithm Choice

JAVA(5 lines)
Code
Loading syntax highlighter...

2. Quick Sort Worst Case

JAVA(5 lines)
Code
Loading syntax highlighter...

3. Forgetting Stability Needs

JAVA(6 lines)
Code
Loading syntax highlighter...

4. Modifying During Sort

JAVA(5 lines)
Code
Loading syntax highlighter...

🎯 Interview Practice

Test your sorting algorithm knowledge with 10 curated interview questions:

QuickSort (Interview Mode)
O(n log n) avg
1 / 37
Initial array - starting QuickSort
Stable:Merge sort, Insertion sort (keeps equal element order)
In-place:Quick sort, Heap sort (O(1) extra space)
64
[0]
34
[1]
25
[2]
12
[3]
22
[4]
11
[5]
90
[6]
Pivot will be selected...
Speed
Comparing
Comparing
Swapping
Swapping
Sorted
Sorted
Pivot
Pivot
P · [ ] · R
Loading visualizer...

🎤 Interview Tips

Q: Which sorting algorithm does Java use?

"

For primitives: Dual-Pivot QuickSort. For objects: TimSort (a hybrid of merge sort and insertion sort). TimSort is stable, QuickSort is not.

Q: When would you use O(n²) algorithms?

"

For small arrays (n < 50), insertion sort is often fastest due to low overhead. Also useful when data is nearly sorted.

Q: How does QuickSort achieve O(n log n) average?

"

On average, the pivot splits the array roughly in half, giving log n levels of recursion, each doing O(n) work total. Worst case (already sorted with bad pivot) degrades to O(n²).

Q: What is TimSort?

"

A hybrid algorithm combining merge sort and insertion sort. It identifies "runs" (sorted subsequences) and merges them efficiently. Optimized for real-world data that often has existing order.

Previous: Part 9: Binary Search

Next: Part 11: Graph Traversal (DFS & BFS)

Visualizers: Sorting, SortingComparison from @tomaszjarosz/react-visualizers