What is Sorting?

■ MASTERCLASS SERIES ■

Sorting is the process of arranging elements of a list or array in a specific order (ascending or descending). It is one of

SORTING
the most fundamental operations in computer science — virtually every application relies on sorted data for efficient
searching, merging, and reporting.

■ Why Sorting Matters

Binary Search requires sorted data → O(log n) vs O(n) for linear search

ALGORITHMS
Database queries, file systems, UI rendering all rely on sorted structures
Many algorithms (e.g., closest pair, convex hull) need sorted input
Sorting is a standard measure of algorithm efficiency and design skill

Sorting Algorithm Properties

The Complete Professional Reference
Every sorting algorithm can be described along these key axes:

Property Description Example

Stable Equal elements maintain original relative order Merge Sort, Insertion Sort
Bubble Sort Selection Sort Insertion Sort Merge Sort Quick Sort
Unstable Equal elements may be reordered Quick Sort, Heap Sort

In-place Sorts using O(1) extra memory Bubble, Selection, Insertion

■
Out-of-place
■ ■
Requires additional memory proportional to input
■ Merge Sort
■
Comparison-based Compares elements to determine order All 5 algorithms here
Pseudocode Python Impl. C++ Impl. LeetCode Probs Complexity Analysis
Non-comparison Uses element values directly (counting, radix) Counting Sort, Radix Sort

Adaptive Faster when input is nearly sorted Insertion Sort, Tim Sort

Online Can sort as data arrives Insertion Sort

Master Complexity Comparison

Algorithm Best Average 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

■ Color guide: Best(green) O(n) = linear · O(n log n) = good · O(n²) = poor for large n
Space O(1) = in-place · O(log n) = recursive stack · O(n) = auxiliary array

Time Complexity ● Space Complexity ● When to Use ● Visual Walkthroughs

Step-by-Step Explanations ● Full Source Code ● LeetCode Problem Mapping
{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

1 Bubble Sort ALGORITHM

Comparison · Stable · In-Place · Adaptive #0

How It Works

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong
order. The largest unsorted element 'bubbles up' to its correct position at the end of each pass. After n-1 passes, the
array is fully sorted.

Bubble Sort — Step-by-Step on [5, 3, 8, 4, 2]

Initial state: [ 5 3 8 4 2 ]

Pass 1 — bubble max: [ 3 5 4 2 | 8 ] ← 8 bubbled up

Pass 2: [ 3 4 2 | 5 8 ] ← 5 bubbled up

Pass 3: [ 3 2 | 4 5 8 ] ← 4 bubbled up

Pass 4: [ 2 | 3 4 5 8 ] ← 3 bubbled up

Sorted: [ 2 3 4 5 8 ] ✓ Done!

Pseudocode

Pseudocode TEXT

1 ALGORITHM BubbleSort(arr, n):

2 for i = 0 to n-2:
3 swapped = false
4 for j = 0 to n-2-i:
5 if arr[j] > arr[j+1]:
6 SWAP(arr[j], arr[j+1])
7 swapped = true
8 if swapped == false:
9 BREAK // Already sorted — early exit
10 return arr

Python Implementation

masterclass · sorting algorithms Page 2

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

bubble_sort.py PYTHON

1 def bubble_sort(arr):
2 """
3 Bubble Sort with early-exit optimisation.
4 Time: O(n) best, O(n^2) average/worst
5 Space: O(1) — in-place
6 """
7 n = len(arr)
8 for i in range(n - 1):
9 swapped = False
10 # Last i elements are already sorted
11 for j in range(0, n - 1 - i):
12 if arr[j] > arr[j + 1]:
13 arr[j], arr[j + 1] = arr[j + 1], arr[j]
14 swapped = True
15 # Optimisation: stop if no swaps in this pass
16 if not swapped:
17 break
18 return arr
19
20
21 # ■■ Test ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
22 if __name__ == "__main__":
23 data = [64, 34, 25, 12, 22, 11, 90]
24 print("Before:", data)
25 result = bubble_sort(data)
26 print("After: ", result)
27 # Output: After: [11, 12, 22, 25, 34, 64, 90]

C++ Implementation

masterclass · sorting algorithms Page 3

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

bubble_sort.cpp CPP

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 void bubbleSort(vector<int>& arr) {
7 int n = [Link]();
8 for (int i = 0; i < n - 1; i++) {
9 bool swapped = false;
10 // After each pass, largest element is at end
11 for (int j = 0; j < n - 1 - i; j++) {
12 if (arr[j] > arr[j + 1]) {
13 swap(arr[j], arr[j + 1]);
14 swapped = true;
15 }
16 }
17 // Early exit if already sorted
18 if (!swapped) break;
19 }
20 }
21
22 int main() {
23 vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
24 bubbleSort(arr);
25 for (int x : arr) cout << x << " ";
26 // Output: 11 12 22 25 34 64 90
27 return 0;
28 }

Complexity Analysis

O(n) O(n²) O(n²) O(1) Yes

Best Case Average Case Worst Case Space Stable

✓ Best Case O(n): Array is already sorted → 0 swaps, 1 pass with early-exit optimisation
Worst Case O(n²): Array is reverse sorted → n(n-1)/2 comparisons and swaps
The key optimisation: track swapped flag — if no swaps in a pass, list is sorted!

When to Use Bubble Sort

■ USE Bubble Sort when:

✓ Array is small (n < 20) and simplicity is preferred
✓ Array is nearly sorted — it achieves O(n) with the optimisation
✓ Teaching / learning purposes — intuitive concept
✗ AVOID for large datasets — O(n²) is prohibitively slow
✗ AVOID when performance matters — Merge Sort or Quick Sort preferred

LeetCode Problems — Bubble Sort

No. Problem Difficulty Relation Tag

masterclass · sorting algorithms Page 4

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

#75 Sort Colors Medium Partition-based, similar swaps

Classic

#283 Move Zeroes Easy Adjacent swaps like bubbleCommon

#912 Sort an Array Medium Implement any sort from scratch

Must-Do

#1122 Relative Sort Array Easy Frequency + sort combo Good

#969 Pancake Sorting Medium Selection-bubble variant Fun

LC #283 Solution PYTHON

1 # LC #283 — Move Zeroes (Bubble Sort concept)

2 # Move all zeros to end maintaining relative order
3 def moveZeroes(nums):
4 # Bubble non-zeros to front (adjacent swap style)
5 pos = 0 # position for next non-zero element
6 for i in range(len(nums)):
7 if nums[i] != 0:
8 nums[pos], nums[i] = nums[i], nums[pos]
9 pos += 1
10 return nums
11
12 # Input: [0, 1, 0, 3, 12]
13 # Output: [1, 3, 12, 0, 0]

masterclass · sorting algorithms Page 5

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

2 Selection Sort ALGORITHM

Comparison · Unstable · In-Place · Not Adaptive #0

How It Works

Selection Sort divides the array into a sorted and unsorted region. On each pass, it SELECTS the minimum element
from the unsorted region and places it at the beginning of that region (by swapping with the first unsorted element).
Repeat until sorted.

Selection Sort — Step-by-Step on [29, 10, 14, 37, 13]

Initial: [ 29 10 14 37 13 ]

Pass 1 — min=10: [ 10 | 29 14 37 13 ] swap(29,10)

Pass 2 — min=13: [ 10 13 | 29 37 14 ] swap(14... wait: min=13)→ swap(29,13)

Pass 3 — min=14: [ 10 13 14 | 37 29 ] swap(29,14)

Pass 4 — min=29: [ 10 13 14 29 | 37 ] swap(37,29)

Sorted: [ 10 13 14 29 37 ] ✓ Done! (4 swaps total)

Pseudocode

Pseudocode TEXT

1 ALGORITHM SelectionSort(arr, n):

2 for i = 0 to n-2:
3 min_idx = i
4 for j = i+1 to n-1:
5 if arr[j] < arr[min_idx]:
6 min_idx = j
7 // Place minimum at front of unsorted region
8 if min_idx != i:
9 SWAP(arr[i], arr[min_idx])
10 return arr

Python Implementation

masterclass · sorting algorithms Page 6

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

selection_sort.py PYTHON

1 def selection_sort(arr):
2 """
3 Selection Sort — always O(n^2), max n-1 swaps.
4 Time: O(n^2) for all cases
5 Space: O(1) — in-place
6 Stable: NO (swap can skip over equal elements)
7 """
8 n = len(arr)
9 for i in range(n - 1):
10 # Find the minimum in arr[i..n-1]
11 min_idx = i
12 for j in range(i + 1, n):
13 if arr[j] < arr[min_idx]:
14 min_idx = j
15 # Swap the found minimum with the first element
16 if min_idx != i:
17 arr[i], arr[min_idx] = arr[min_idx], arr[i]
18 return arr
19
20
21 # Stable version — shift instead of swap
22 def selection_sort_stable(arr):
23 n = len(arr)
24 for i in range(n):
25 min_idx = i
26 for j in range(i + 1, n):
27 if arr[j] < arr[min_idx]:
28 min_idx = j
29 # Shift right instead of swap to preserve stability
30 key = arr[min_idx]
31 while min_idx > i:
32 arr[min_idx] = arr[min_idx - 1]
33 min_idx -= 1
34 arr[i] = key
35 return arr
36
37
38 if __name__ == "__main__":
39 data = [29, 10, 14, 37, 13]
40 print("Sorted:", selection_sort(data))
41 # Output: Sorted: [10, 13, 14, 29, 37]

C++ Implementation

masterclass · sorting algorithms Page 7

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

selection_sort.cpp CPP

1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 void selectionSort(vector<int>& arr) {
6 int n = [Link]();
7 for (int i = 0; i < n - 1; i++) {
8 // Find minimum element in arr[i..n-1]
9 int min_idx = i;
10 for (int j = i + 1; j < n; j++) {
11 if (arr[j] < arr[min_idx])
12 min_idx = j;
13 }
14 // Swap if minimum is not at current position
15 if (min_idx != i)
16 swap(arr[i], arr[min_idx]);
17 }
18 }
19
20 // Finding k-th smallest — Selection Sort partial run
21 int kthSmallest(vector<int> arr, int k) {
22 int n = [Link]();
23 for (int i = 0; i < k; i++) {
24 int min_idx = i;
25 for (int j = i + 1; j < n; j++)
26 if (arr[j] < arr[min_idx]) min_idx = j;
27 swap(arr[i], arr[min_idx]);
28 }
29 return arr[k - 1]; // k-th smallest
30 }
31
32 int main() {
33 vector<int> arr = {29, 10, 14, 37, 13};
34 selectionSort(arr);
35 for (int x : arr) cout << x << " ";
36 // Output: 10 13 14 29 37
37 }

O(n²) O(n²) O(n²) O(1) O(n)

Best Case Average Worst Case Space Swaps

■ Key Insight: Selection Sort always does exactly n-1 swaps (or fewer) — great when write cost is high!
Best Case = Worst Case = O(n²): It always scans the full unsorted region regardless
Despite O(n²), it often outperforms Bubble Sort in practice due to fewer writes/swaps
Unstable: [2a, 2b, 1] → [1, 2b, 2a] — swapping can reorder equal elements

LeetCode Problems — Selection Sort

No. Problem Difficulty Relation Tag

#215 Kth Largest Element Medium Selection partial sort Classic

#347 Top K Frequent Elements Medium Partial selection + heap Must-Do

#973 K Closest Points Medium Partial sort concept Common

masterclass · sorting algorithms Page 8

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

#912 Sort an Array Medium Implement selection sort Practice

#414 Third Max Number Easy Find 3rd max via selection Easy

masterclass · sorting algorithms Page 9

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

3 Insertion Sort ALGORITHM

Comparison · Stable · In-Place · Adaptive · Online #0

How It Works

Insertion Sort builds the sorted array one element at a time. It picks the next element from the unsorted region and
INSERTS it into its correct position in the sorted region by shifting larger elements one position to the right. Like
sorting playing cards in your hand.

Insertion Sort — Step-by-Step on [5, 2, 4, 6, 1, 3]

Initial: [ 5 | 2 4 6 1 3 ]

Insert 2: [ 2 5 | 4 6 1 3 ] 2<5, shift 5 right

Insert 4: [ 2 4 5 | 6 1 3 ] 4<5, shift 5

Insert 6: [ 2 4 5 6 | 1 3 ] 6>5, no shift needed

Insert 1: [ 1 2 4 5 6 | 3 ] 1 < all, shift all

Insert 3: [ 1 2 3 4 5 6 ] ✓ Sorted!

Pseudocode

Pseudocode TEXT

1 ALGORITHM InsertionSort(arr, n):

2 for i = 1 to n-1:
3 key = arr[i] // Element to insert
4 j = i - 1 // Start from last sorted element
5 while j >= 0 AND arr[j] > key:
6 arr[j+1] = arr[j] // Shift right
7 j = j - 1
8 arr[j+1] = key // Place key in correct position
9 return arr

Python Implementation

masterclass · sorting algorithms Page 10

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

insertion_sort.py PYTHON

1 def insertion_sort(arr):
2 """
3 Insertion Sort — excellent for small/nearly-sorted arrays.
4 Time: O(n) best, O(n^2) avg/worst
5 Space: O(1) in-place
6 Stable: YES — equal elements never swap relative order
7 Online: YES — can sort as new elements arrive
8 """
9 for i in range(1, len(arr)):
10 key = arr[i] # Current element to place
11 j = i - 1
12 # Shift elements greater than key to right
13 while j >= 0 and arr[j] > key:
14 arr[j + 1] = arr[j]
15 j -= 1
16 arr[j + 1] = key # Insert key at correct spot
17 return arr
18
19
20 # Binary Insertion Sort — O(n log n) comparisons, O(n^2) shifts
21 import bisect
22 def binary_insertion_sort(arr):
23 for i in range(1, len(arr)):
24 key = arr[i]
25 # Find position using binary search O(log n)
26 pos = bisect.bisect_left(arr, key, 0, i)
27 # Shift and insert
28 arr[pos + 1:i + 1] = arr[pos:i]
29 arr[pos] = key
30 return arr
31
32
33 if __name__ == "__main__":
34 data = [5, 2, 4, 6, 1, 3]
35 print("Sorted:", insertion_sort(data))
36 # Output: Sorted: [1, 2, 3, 4, 5, 6]
37 nearly_sorted = [1, 2, 3, 5, 4, 6] # Best case ~ O(n)
38 print("Nearly sorted:", insertion_sort(nearly_sorted))

C++ Implementation

masterclass · sorting algorithms Page 11

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

insertion_sort.cpp CPP

1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 void insertionSort(vector<int>& arr) {
6 int n = [Link]();
7 for (int i = 1; i < n; i++) {
8 int key = arr[i];
9 int j = i - 1;
10 // Move elements > key one position ahead
11 while (j >= 0 && arr[j] > key) {
12 arr[j + 1] = arr[j];
13 j--;
14 }
15 arr[j + 1] = key;
16 }
17 }
18
19 // Generalized template version
20 template <typename T>
21 void insertionSort(vector<T>& arr) {
22 int n = [Link]();
23 for (int i = 1; i < n; i++) {
24 T key = arr[i];
25 int j = i - 1;
26 while (j >= 0 && arr[j] > key) {
27 arr[j + 1] = arr[j]; j--;
28 }
29 arr[j + 1] = key;
30 }
31 }
32
33 int main() {
34 vector<int> arr = {5, 2, 4, 6, 1, 3};
35 insertionSort(arr);
36 for (int x : arr) cout << x << " ";
37 // Output: 1 2 3 4 5 6
38 return 0;
39 }

O(n) O(n²) O(n²) O(1) Yes

Best Case Average Worst Case Space Stable

✓ Insertion Sort is the FASTEST algorithm for small arrays (n<20) and nearly-sorted data
Python's built-in sort (Timsort) and Java's [Link] use Insertion Sort for n<47
Online algorithm: can sort a stream of data as it arrives — no need to wait for all input
Binary Insertion reduces comparisons to O(n log n) but shifts remain O(n²)

LeetCode Problems — Insertion Sort

No. Problem Difficulty Relation Tag

#147 Insertion Sort List Medium Exact algorithm on linked list

Must-Do

#148 Sort List Medium Merge sort on list (compare)

Hard

#315 Count of Smaller Numbers Hard Insertion + BIT/merge Classic

masterclass · sorting algorithms Page 12

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

#905 Sort Array by Parity Easy Partition-like insertion Easy

#1365 How Many Smaller Numbers Easy Counting + insertion idea Good

LC #147 Solution PYTHON

1 # LC #147 — Insertion Sort List (Exact Algorithm)

2 class ListNode:
3 def __init__(self, val=0, next=None):
4 [Link] = val
5 [Link] = next
6
7 def insertionSortList(head):
8 dummy = ListNode(0) # Sorted list starts empty
9 curr = head
10 while curr:
11 next_node = [Link] # Save next
12 # Find correct position in sorted list
13 prev = dummy
14 while [Link] and [Link] < [Link]:
15 prev = [Link]
16 # Insert curr after prev
17 [Link] = [Link]
18 [Link] = curr
19 curr = next_node
20 return [Link]

masterclass · sorting algorithms Page 13

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

4 Merge Sort ALGORITHM

Divide & Conquer · Stable · Out-of-Place · Guaranteed O(n log n) #0

How It Works

Merge Sort follows the Divide and Conquer paradigm. It recursively divides the array into two halves until each
sub-array has one element (already sorted), then MERGES them back in sorted order. The merge step is where the
real work happens — it's a linear-time operation to merge two sorted arrays.

Merge Sort — Divide & Conquer on [38, 27, 43, 3, 9, 82, 10]

Split L1: [38 27 43 3] [9 82 10]

Split L2: [38 27] [43 3] [9 82] [10]

Split L3: [38] [27] [43] [3] [9] [82] [10]

Merge L3: [27 38] [3 43] [9 82] [10]

Merge L2: [3 27 38 43] [9 10 82]

Merge L1: [3 9 10 27 38 43 82] ✓ Sorted!

Pseudocode

Pseudocode TEXT

1 ALGORITHM MergeSort(arr, left, right):

2 if left < right:
3 mid = (left + right) / 2
4 MergeSort(arr, left, mid) // Sort left half
5 MergeSort(arr, mid+1, right) // Sort right half
6 Merge(arr, left, mid, right) // Combine
7
8 ALGORITHM Merge(arr, left, mid, right):
9 Create L = arr[left..mid]
10 Create R = arr[mid+1..right]
11 i = 0, j = 0, k = left
12 while i < len(L) AND j < len(R):
13 if L[i] <= R[j]: arr[k] = L[i]; i++
14 else: arr[k] = R[j]; j++
15 k++
16 Copy remaining elements of L and R into arr

Python Implementation

masterclass · sorting algorithms Page 14

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

merge_sort.py PYTHON

1 def merge_sort(arr):
2 """
3 Merge Sort — guaranteed O(n log n) all cases.
4 Time: O(n log n) for all cases
5 Space: O(n) auxiliary array
6 Stable: YES — merge preserves order of equal elements
7 Best For: Linked lists, external sorting, stable sort needed
8 """
9 if len(arr) <= 1:
10 return arr
11
12 # Divide
13 mid = len(arr) // 2
14 left = merge_sort(arr[:mid])
15 right = merge_sort(arr[mid:])
16
17 # Conquer (merge)
18 return _merge(left, right)
19
20
21 def _merge(left, right):
22 """Merge two sorted arrays into one sorted array."""
23 result = []
24 i = j = 0
25 while i < len(left) and j < len(right):
26 if left[i] <= right[j]: # <= preserves stability
27 [Link](left[i])
28 i += 1
29 else:
30 [Link](right[j])
31 j += 1
32 [Link](left[i:]) # Remaining elements
33 [Link](right[j:])
34 return result
35
36
37 # In-place merge sort (less memory but complex)
38 def merge_sort_inplace(arr, left, right):
39 if left < right:
40 mid = (left + right) // 2
41 merge_sort_inplace(arr, left, mid)
42 merge_sort_inplace(arr, mid + 1, right)
43 _merge_inplace(arr, left, mid, right)
44
45 def _merge_inplace(arr, left, mid, right):
46 L = arr[left:mid + 1]
47 R = arr[mid + 1:right + 1]
48 i = j = 0
49 k = left
50 while i < len(L) and j < len(R):
51 if L[i] <= R[j]: arr[k] = L[i]; i += 1
52 else: arr[k] = R[j]; j += 1
53 k += 1
54 while i < len(L): arr[k] = L[i]; i += 1; k += 1
55 while j < len(R): arr[k] = R[j]; j += 1; k += 1
56
57 if __name__ == "__main__":
58 data = [38, 27, 43, 3, 9, 82, 10]
59 print("Sorted:", merge_sort(data))
60 # Output: Sorted: [3, 9, 10, 27, 38, 43, 82]

C++ Implementation

masterclass · sorting algorithms Page 15

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

merge_sort.cpp CPP

1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 void merge(vector<int>& arr, int left, int mid, int right) {
6 // Sizes of subarrays
7 int n1 = mid - left + 1;
8 int n2 = right - mid;
9 // Temp arrays
10 vector<int> L([Link]()+left, [Link]()+mid+1);
11 vector<int> R([Link]()+mid+1, [Link]()+right+1);
12 int i = 0, j = 0, k = left;
13 while (i < n1 && j < n2) {
14 if (L[i] <= R[j]) arr[k++] = L[i++];
15 else arr[k++] = R[j++];
16 }
17 while (i < n1) arr[k++] = L[i++];
18 while (j < n2) arr[k++] = R[j++];
19 }
20
21 void mergeSort(vector<int>& arr, int left, int right) {
22 if (left >= right) return; // Base case
23 int mid = left + (right - left) / 2; // Avoids overflow
24 mergeSort(arr, left, mid);
25 mergeSort(arr, mid + 1, right);
26 merge(arr, left, mid, right);
27 }
28
29 int main() {
30 vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
31 mergeSort(arr, 0, [Link]() - 1);
32 for (int x : arr) cout << x << " ";
33 // Output: 3 9 10 27 38 43 82
34 return 0;
35 }

O(n log n) O(n log n) O(n log n) O(n) Yes

Best Case Average Worst Case Space Stable

✓ Merge Sort GUARANTEES O(n log n) — no worst-case degradation like Quick Sort
Best choice for sorting Linked Lists (no random access needed, uses pointer rearrangement)
Used in External Sorting (large files that don't fit in memory — merge chunks)
Python's Timsort (built-in sort) is based on Merge Sort + Insertion Sort
Trade-off: Requires O(n) extra space — use Quick Sort if memory is tight

LeetCode Problems — Merge Sort

No. Problem Difficulty Relation Tag

#88 Merge Sorted Array Easy Core merge step Must-Do

#148 Sort List Medium Merge sort on linked list Classic

#315 Count of Smaller Numbers Hard Modified merge sort Hard

masterclass · sorting algorithms Page 16

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

#493 Reverse Pairs Hard Merge sort + count Hard

#327 Count of Range Sum Hard Divide & conquer merge Hard

#23 Merge k Sorted Lists Hard K-way merge Must-Do

LC #88 & #315 Solutions PYTHON

1 # LC #88 — Merge Sorted Array (Core Merge step)

2 # Merge nums2 into nums1 (has extra space at end)
3 def merge(nums1, m, nums2, n):
4 # Fill from the back to avoid overwrites
5 i, j, k = m - 1, n - 1, m + n - 1
6 while i >= 0 and j >= 0:
7 if nums1[i] > nums2[j]:
8 nums1[k] = nums1[i]; i -= 1
9 else:
10 nums1[k] = nums2[j]; j -= 1
11 k -= 1
12 # Copy remaining nums2 elements
13 nums1[:j + 1] = nums2[:j + 1]
14
15 # LC #315 — Count of Smaller (Modified Merge Sort)
16 def countSmaller(nums):
17 result = [0] * len(nums)
18 indexed = list(enumerate(nums)) # Track original indices
19
20 def merge_sort(arr):
21 if len(arr) <= 1: return arr
22 mid = len(arr) // 2
23 left = merge_sort(arr[:mid])
24 right = merge_sort(arr[mid:])
25 merged, i, j = [], 0, 0
26 while i < len(left) and j < len(right):
27 if left[i][1] <= right[j][1]:
28 result[left[i][0]] += j # j elements from right are smaller
29 [Link](left[i]); i += 1
30 else:
31 [Link](right[j]); j += 1
32 for node in left[i:]:
33 result[node[0]] += j
34 [Link](node)
35 return merged + right[j:]
36
37 merge_sort(indexed)
38 return result

masterclass · sorting algorithms Page 17

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

5 Quick Sort ALGORITHM

Divide & Conquer · Unstable · In-Place · Cache-Friendly #0

How It Works

Quick Sort selects a PIVOT element and PARTITIONS the array so all elements less than pivot go left, all greater go
right. The pivot is then in its final sorted position. Recursively sort left and right sub-arrays. It's the most widely used
sort in practice due to excellent cache performance and O(n log n) average case.

Quick Sort — Lomuto Partition on [10, 80, 30, 90, 40, 50, 70]

Initial (pivot=70): [10 80 30 90 40 50 | 70 ] pivot = last element

Partition: [10 30 40 50 70 80 90 ] pivot 70 in final position!

Left sub [10..50]: [10 30 40 50] recurse

Right sub [80,90]: [80 90] recurse

Final sorted: [10 30 40 50 70 80 90] ✓ Done!

Pseudocode — Lomuto Partition

Pseudocode TEXT

1 ALGORITHM QuickSort(arr, low, high):

2 if low < high:
3 pi = Partition(arr, low, high) // pi = pivot index
4 QuickSort(arr, low, pi - 1) // Sort left of pivot
5 QuickSort(arr, pi + 1, high) // Sort right of pivot
6
7 ALGORITHM Partition(arr, low, high): // Lomuto Scheme
8 pivot = arr[high] // Choose last as pivot
9 i = low - 1 // Index of smaller element
10 for j = low to high - 1:
11 if arr[j] <= pivot:
12 i++
13 SWAP(arr[i], arr[j])
14 SWAP(arr[i+1], arr[high]) // Place pivot in position
15 return i + 1 // Pivot index

Python Implementation

masterclass · sorting algorithms Page 18

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

quick_sort.py — All Partition Schemes PYTHON

1 import random
2
3 # 1. Lomuto Partition — pivot = last element
4 def _lomuto(arr, low, high):
5 pivot, i = arr[high], low - 1
6 for j in range(low, high):
7 if arr[j] <= pivot:
8 i += 1; arr[i], arr[j] = arr[j], arr[i]
9 arr[i+1], arr[high] = arr[high], arr[i+1]
10 return i + 1
11
12 def quick_sort(arr, low=None, high=None):
13 if low is None: low, high = 0, len(arr)-1
14 if low < high:
15 pi = _lomuto(arr, low, high)
16 quick_sort(arr, low, pi-1)
17 quick_sort(arr, pi+1, high)
18 return arr
19
20 # 2. Hoare Partition — pivot = first element, fewer swaps
21 def _hoare(arr, low, high):
22 pivot, i, j = arr[low], low-1, high+1
23 while True:
24 i += 1
25 while arr[i] < pivot: i += 1
26 j -= 1
27 while arr[j] > pivot: j -= 1
28 if i >= j: return j
29 arr[i], arr[j] = arr[j], arr[i]
30
31 def quick_sort_hoare(arr, low=None, high=None):
32 if low is None: low, high = 0, len(arr)-1
33 if low < high:
34 pi = _hoare(arr, low, high)
35 quick_sort_hoare(arr, low, pi)
36 quick_sort_hoare(arr, pi+1, high)
37 return arr
38
39 # 3. Randomized — avoids O(n^2) worst case
40 def quick_sort_random(arr, low=None, high=None):
41 if low is None: low, high = 0, len(arr)-1
42 if low < high:
43 r = [Link](low, high)
44 arr[r], arr[high] = arr[high], arr[r]
45 pi = _lomuto(arr, low, high)
46 quick_sort_random(arr, low, pi-1)
47 quick_sort_random(arr, pi+1, high)
48 return arr
49
50 # 4. 3-Way — for many duplicates (Dutch National Flag)
51 def quick_sort_3way(arr, low=None, high=None):
52 if low is None: low, high = 0, len(arr)-1
53 if low >= high: return arr
54 lt, gt, pivot, i = low, high, arr[low], low+1
55 while i <= gt:
56 if arr[i] < pivot:
57 arr[lt], arr[i] = arr[i], arr[lt]; lt+=1; i+=1
58 elif arr[i] > pivot:
59 arr[i], arr[gt] = arr[gt], arr[i]; gt-=1
60 else: i+=1
61 quick_sort_3way(arr, low, lt-1)
62 quick_sort_3way(arr, gt+1, high)
63 return arr
64
65 if __name__ == "__main__":
66 data = [10, 80, 30, 90, 40, 50, 70]
67 for fn in [quick_sort, quick_sort_hoare, quick_sort_random, quick_sort_3way]:
68 print(fn.__name__, ":", fn(data[:]))
69 # All → [10, 30, 40, 50, 70, 80, 90]

C++ Implementation

masterclass · sorting algorithms Page 19

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

quick_sort.cpp CPP

1 #include <iostream>
2 #include <vector>
3 #include <algorithm> // for swap
4 #include <cstdlib> // for rand
5 using namespace std;
6
7 int partition(vector<int>& arr, int low, int high) {
8 // Median-of-three pivot for better performance
9 int mid = low + (high - low) / 2;
10 if (arr[mid] < arr[low]) swap(arr[low], arr[mid]);
11 if (arr[high] < arr[low]) swap(arr[low], arr[high]);
12 if (arr[mid] < arr[high]) swap(arr[mid], arr[high]);
13 int pivot = arr[high]; // Now pivot is median
14 int i = low - 1;
15 for (int j = low; j < high; j++) {
16 if (arr[j] <= pivot) {
17 i++;
18 swap(arr[i], arr[j]);
19 }
20 }
21 swap(arr[i + 1], arr[high]);
22 return i + 1;
23 }
24
25 void quickSort(vector<int>& arr, int low, int high) {
26 if (low < high) {
27 int pi = partition(arr, low, high);
28 quickSort(arr, low, pi - 1);
29 quickSort(arr, pi + 1, high);
30 }
31 }
32
33 // Iterative Quick Sort (avoids stack overflow for large n)
34 void quickSortIterative(vector<int>& arr, int low, int high) {
35 vector<int> stack(high - low + 1);
36 int top = -1;
37 stack[++top] = low;
38 stack[++top] = high;
39 while (top >= 0) {
40 high = stack[top--];
41 low = stack[top--];
42 int pi = partition(arr, low, high);
43 if (pi - 1 > low) { stack[++top] = low; stack[++top] = pi-1; }
44 if (pi + 1 < high) { stack[++top] = pi+1; stack[++top] = high; }
45 }
46 }
47
48 int main() {
49 vector<int> arr = {10, 80, 30, 90, 40, 50, 70};
50 quickSort(arr, 0, [Link]() - 1);
51 for (int x : arr) cout << x << " ";
52 // Output: 10 30 40 50 70 80 90
53 return 0;
54 }

O(n log n) O(n log n) O(n²) O(log n) No

Best Case Average Worst Case Space Stable

masterclass · sorting algorithms Page 20

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

■ Worst Case O(n²): Happens when pivot is always min/max (sorted or reverse-sorted array)
Fix 1: Randomized pivot makes O(n²) astronomically unlikely in practice
Fix 2: Median-of-three pivot selection (first, mid, last) — industry standard
3-Way partitioning (Dutch National Flag) handles duplicates in O(n) — e.g. all same elements
Quick Sort is typically 2-3x faster than Merge Sort in practice due to cache locality

Pivot Selection Strategies

Pivot Selection Strategies PYTHON

1 # Strategy 1: First element (Naive — bad for sorted input)

2 pivot = arr[low] # O(n^2) when array is sorted/reverse-sorted
3
4 # Strategy 2: Last element (Lomuto — same issue)
5 pivot = arr[high]
6
7 # Strategy 3: Median of Three (Recommended)
8 def median_of_three(arr, low, high):
9 mid = (low + high) // 2
10 # Sort low, mid, high and use mid as pivot
11 if arr[low] > arr[mid]: arr[low], arr[mid] = arr[mid], arr[low]
12 if arr[low] > arr[high]: arr[low], arr[high] = arr[high], arr[low]
13 if arr[mid] > arr[high]: arr[mid], arr[high] = arr[high], arr[mid]
14 arr[mid], arr[high] = arr[high], arr[mid] # Place pivot at high
15 return arr[high]
16
17 # Strategy 4: Random Pivot (Simple and effective)
18 import random
19 pivot_idx = [Link](low, high)
20 arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
21 pivot = arr[high]

LeetCode Problems — Quick Sort

No. Problem Difficulty Relation Tag

#215 Kth Largest Element Medium Quickselect (partial QS) Must-Do

#75 Sort Colors Medium 3-way partition DNF Classic

#912 Sort an Array Medium Implement Quick Sort Practice

#973 K Closest Points Medium Quickselect variant Common

#324 Wiggle Sort II Medium Median + 3-way partition Hard

#347 Top K Frequent Medium Quickselect on frequency Good

masterclass · sorting algorithms Page 21

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

LC #215 QuickSelect & LC #75 DNF PYTHON

1 # LC #215 — Kth Largest (QuickSelect — Average O(n)!)

2 # QuickSelect: like Quick Sort but only recurse into ONE side
3 import random
4
5 def findKthLargest(nums, k):
6 """Find k-th largest in average O(n) time."""
7 k = len(nums) - k # Convert to k-th smallest index
8
9 def quickselect(lo, hi):
10 if lo == hi: return nums[lo]
11 # Random pivot
12 pivot_idx = [Link](lo, hi)
13 nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
14 pivot = nums[hi]
15 store = lo
16 for i in range(lo, hi):
17 if nums[i] <= pivot:
18 nums[store], nums[i] = nums[i], nums[store]
19 store += 1
20 nums[store], nums[hi] = nums[hi], nums[store]
21 # Only recurse into the relevant partition
22 if store == k: return nums[store]
23 elif store < k: return quickselect(store + 1, hi)
24 else: return quickselect(lo, store - 1)
25
26 return quickselect(0, len(nums) - 1)
27
28 # LC #75 — Sort Colors (3-Way Dutch National Flag)
29 def sortColors(nums):
30 low, mid, high = 0, 0, len(nums) - 1
31 while mid <= high:
32 if nums[mid] == 0:
33 nums[low], nums[mid] = nums[mid], nums[low]
34 low += 1; mid += 1
35 elif nums[mid] == 1:
36 mid += 1
37 else:
38 nums[mid], nums[high] = nums[high], nums[mid]
39 high -= 1
40 # Reds(0) | Whites(1) | Blues(2)

masterclass · sorting algorithms Page 22

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

Master Decision Guide — Which Sort to Use?

Algorithm Decision Tree TEXT

1 # DECISION TREE: Choosing the Right Sorting Algorithm

2
3 Is n small? (n < 20)
4 ■■ YES → Use INSERTION SORT (fastest for tiny arrays)
5 ■■ NO
6 Is data nearly sorted? (< 10% inversions)
7 ■■ YES → Use INSERTION SORT (O(n) for nearly sorted)
8 ■■ NO
9 Is stability required? (equal elements preserve order)
10 ■■ YES → Use MERGE SORT (guaranteed stable O(n log n))
11 ■ Or TIMSORT (Python built-in — merge + insertion)
12 ■■ NO
13 Is memory a constraint? (O(1) space required)
14 ■■ YES → Use QUICK SORT (in-place, O(log n) stack)
15 ■ Use HEAP SORT if worst-case guarantee needed
16 ■■ NO
17 Are there many duplicate values?
18 ■■ YES → Use QUICK SORT 3-WAY partition
19 ■ Or COUNTING SORT if range is small
20 ■■ NO
21 General case:
22 → QUICK SORT (fastest average, cache-friendly)
23 → MERGE SORT (if stability needed or linked list)

Practical Performance Benchmarks

These are approximate timings on modern hardware. Actual results vary by system, data patterns, and
implementation quality.

Algorithm n=1K n=10K n=100K n=1M Notes

Bubble Sort ~1ms ~100ms ~10s Unusable Only for tiny n

Selection Sort ~0.8ms ~80ms ~8s Unusable Min writes

Insertion Sort ~0.5ms ~50ms ~5s Unusable Best if nearly sorted

Merge Sort ~0.05ms ~0.5ms ~6ms ~70ms Stable, consistent

Quick Sort ~0.03ms ~0.3ms ~3.5ms ~42ms Fastest average

Real-World Usage

Where Used Algorithm Why

Python built-in sort Timsort (Merge+Insertion) Adaptive, stable, O(n log n) guaranteed

Java [Link] (primitives) Dual-Pivot Quick Sort Cache friendly, in-place

Java [Link] (objects) Timsort Stability required for objects

C++ std::sort Introsort (QS+HS+IS) Best of all worlds

Database ORDER BY External Merge Sort Data doesn't fit in RAM

Embedded systems Insertion Sort Small n, minimal code size

GPU sorting Bitonic Sort (parallel) Massively parallel comparison networks

masterclass · sorting algorithms Page 23

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

Distributed systems External Merge Sort Multi-way merge of chunks

masterclass · sorting algorithms Page 24

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

Timsort — Python's Built-in Algorithm

Timsort is a hybrid algorithm combining Merge Sort and Insertion Sort. It was designed by Tim Peters in 2002 for
Python and is now used in Python, Java (for objects), Android, and many other platforms. It achieves O(n) on
nearly-sorted data.

Timsort Simplified Implementation PYTHON

1 # Understanding Timsort Concepts

2
3 # Step 1: Split into runs (minimum size = MIN_RUN, ~32-64)
4 MIN_RUN = 32
5
6 def calc_min_run(n):
7 """Find minimum run size — Timsort's first step."""
8 r = 0 # Becomes 1 if any 1 bits are shifted off
9 while n >= MIN_RUN:
10 r |= n & 1
11 n >>= 1
12 return n + r
13
14 def timsort(arr):
15 n = len(arr)
16 min_run = calc_min_run(n)
17
18 # Step 2: Sort individual runs with Insertion Sort
19 for start in range(0, n, min_run):
20 end = min(start + min_run - 1, n - 1)
21 # Insertion sort the run [start..end]
22 for i in range(start + 1, end + 1):
23 key = arr[i]
24 j = i - 1
25 while j >= start and arr[j] > key:
26 arr[j + 1] = arr[j]
27 j -= 1
28 arr[j + 1] = key
29
30 # Step 3: Merge runs using Merge Sort
31 size = min_run
32 while size < n:
33 for start in range(0, n, size * 2):
34 mid = min(n - 1, start + size - 1)
35 end = min(n - 1, start + 2 * size - 1)
36 if mid < end:
37 _merge(arr, start, mid, end)
38 size *= 2
39 return arr
40
41 # Why Timsort wins:
42 # 1. Detects natural runs (already-sorted sequences)
43 # 2. Uses binary search for insertion → O(log n) comparisons per run
44 # 3. Galloping mode: skips large chunks when one run dominates
45 # 4. Stable: equal elements never reordered

Counting Sort & Radix Sort (Non-Comparison)

These algorithms break the O(n log n) lower bound by not comparing elements. They exploit the structure of the data
(integer keys in a known range).

masterclass · sorting algorithms Page 25

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

Counting Sort & Radix Sort PYTHON

1 # Counting Sort — O(n + k) where k = range of values

2 # Use when: integers, bounded range, many duplicates
3 def counting_sort(arr, max_val=None):
4 if not arr: return arr
5 if max_val is None: max_val = max(arr)
6 count = [0] * (max_val + 1)
7 for num in arr: count[num] += 1
8 # Prefix sum for stable version
9 for i in range(1, len(count)): count[i] += count[i-1]
10 output = [0] * len(arr)
11 for num in reversed(arr): # Reverse for stability
12 output[count[num] - 1] = num
13 count[num] -= 1
14 return output
15
16
17 # Radix Sort — O(d * (n + k)), d = digits
18 # Use when: large integers, fixed digit count
19 def radix_sort(arr):
20 max_val = max(arr)
21 exp = 1 # Start with units digit
22 while max_val // exp > 0:
23 arr = _counting_sort_by_digit(arr, exp)
24 exp *= 10
25 return arr
26
27 def _counting_sort_by_digit(arr, exp):
28 n = len(arr)
29 output = [0] * n
30 count = [0] * 10 # 0-9 digits
31 for num in arr: count[(num // exp) % 10] += 1
32 for i in range(1, 10): count[i] += count[i-1]
33 for num in reversed(arr):
34 idx = (num // exp) % 10
35 output[count[idx] - 1] = num
36 count[idx] -= 1
37 return output
38
39 # Example: Sort [170, 45, 75, 90, 802, 24, 2, 66]
40 # After exp=1 (units): [170, 90, 802, 2, 24, 45, 75, 66]
41 # After exp=10 (tens): [802, 2, 24, 45, 66, 170, 75, 90]
42 # After exp=100 (100s): [2, 24, 45, 66, 75, 90, 170, 802]

Complete LeetCode Problem Set — All Algorithms

Sorted by difficulty. Study these in order to master sorting in competitive programming.

# Problem Title Difficulty Algorithm Key Concept

#88 Merge Sorted Array Easy Merge Two-pointer merge

#242 Valid Anagram Easy Sort Sort & compare

#283 Move Zeroes Easy Bubble Adjacent partition

#905 Sort Array by Parity Easy Partition 2-way partition

#414 Third Maximum Number Easy Selection 3-pass selection

#912 Sort an Array Medium Any Implement from scratch

#75 Sort Colors Medium Quick(3-way) Dutch National Flag

#147 Insertion Sort List Medium Insertion Exact algorithm

masterclass · sorting algorithms Page 26

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

#148 Sort List Medium Merge Linked list merge sort

#215 Kth Largest Element Medium QuickSelect Partial sort O(n) avg

#347 Top K Frequent Elements Medium QuickSelect Freq + partial sort

#973 K Closest Points Medium QuickSelect Distance partial sort

#1122 Relative Sort Array Medium Counting Custom comparator

#324 Wiggle Sort II Medium QuickSelect Median + DNF

#315 Count of Smaller Numbers Hard Merge Modified merge sort

#493 Reverse Pairs Hard Merge Count during merge

#327 Count of Range Sum Hard Merge Prefix sum + merge

#23 Merge k Sorted Lists Hard Merge K-way merge heap

#272 Closest BST Values II Hard Merge Merge two sorted lists

masterclass · sorting algorithms Page 27

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

Quick Reference Cheatsheet

Complete Cheatsheet — All 5 Algorithms PYTHON

1 # ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
2 # SORTING ALGORITHMS — COMPLETE CHEATSHEET
3 # ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
4
5 # BUBBLE SORT ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
6 # Adjacent swaps, largest bubbles to end each pass
7 # Best: O(n) Avg: O(n^2) Worst: O(n^2) Space: O(1) Stable: YES
8 def bubble(a):
9 for i in range(len(a)-1):
10 s=False
11 for j in range(len(a)-1-i):
12 if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j]; s=True
13 if not s: break
14 return a
15
16 # SELECTION SORT ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
17 # Find min, swap to front — always n-1 swaps maximum
18 # Best: O(n^2) Avg: O(n^2) Worst: O(n^2) Space: O(1) Stable: NO
19 def selection(a):
20 for i in range(len(a)-1):
21 m=i
22 for j in range(i+1,len(a)):
23 if a[j]<a[m]: m=j
24 a[i],a[m]=a[m],a[i]
25 return a
26
27 # INSERTION SORT ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
28 # Shift larger elements right, insert key at correct spot
29 # Best: O(n) Avg: O(n^2) Worst: O(n^2) Space: O(1) Stable: YES
30 def insertion(a):
31 for i in range(1,len(a)):
32 k,j=a[i],i-1
33 while j>=0 and a[j]>k: a[j+1]=a[j]; j-=1
34 a[j+1]=k
35 return a
36
37 # MERGE SORT ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
38 # Divide → conquer → merge two sorted halves
39 # Best: O(n log n) Avg: O(n log n) Worst: O(n log n) Space: O(n) Stable: YES
40 def merge_sort(a):
41 if len(a)<=1: return a
42 m=len(a)//2; L,R=merge_sort(a[:m]),merge_sort(a[m:])
43 res=[]; i=j=0
44 while i<len(L) and j<len(R):
45 if L[i]<=R[j]: [Link](L[i]); i+=1
46 else: [Link](R[j]); j+=1
47 return res+L[i:]+R[j:]
48
49 # QUICK SORT ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
50 # Partition around pivot, recurse on both sides
51 # Best: O(n log n) Avg: O(n log n) Worst: O(n^2) Space: O(log n) Stable: NO
52 def quick_sort(a,lo=0,hi=None):
53 if hi is None: hi=len(a)-1
54 if lo<hi:
55 i,j,p=lo-1,lo,a[hi]
56 while j<hi:
57 if a[j]<=p: i+=1; a[i],a[j]=a[j],a[i]
58 j+=1
59 a[i+1],a[hi]=a[hi],a[i+1]
60 quick_sort(a,lo,i); quick_sort(a,i+2,hi)
61 return a
62
63 # ■■ TEST ALL ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
64 data = [64, 34, 25, 12, 22, 11, 90]
65 assert bubble(data[:]) == [11,12,22,25,34,64,90]
66 assert selection(data[:]) == [11,12,22,25,34,64,90]
67 assert insertion(data[:]) == [11,12,22,25,34,64,90]
68 assert merge_sort(data[:])== [11,12,22,25,34,64,90]
69 assert quick_sort(data[:])== [11,12,22,25,34,64,90]
70 print("All sorting algorithms verified!")

masterclass · sorting algorithms Page 28

{ } SORTING ALGORITHMS — MASTERCLASS Complete Professional Reference

✓ Golden Rules for Sorting:

1. For n < 20: Use Insertion Sort — lowest constant factor
2. For nearly sorted data: Use Insertion Sort (O(n) adaptive)
3. Need stability: Use Merge Sort or Python's built-in sort()
4. General case: Use Quick Sort (fastest in practice)
5. Memory critical: Use Quick Sort (O(log n) stack space)
6. Guaranteed O(n log n): Use Merge Sort or Heap Sort
7. Integers in small range: Use Counting Sort O(n+k)
8. Large integers, fixed digits: Use Radix Sort O(d*(n+k))
9. Real world: Trust the language built-in (Timsort/Introsort)

masterclass · sorting algorithms Page 29