SORTING ALGOS MEMORIZATION

Core sorting rule

Every sorting algorithm answers: what part is already sorted, and what operation repeats

Binary search requirement

Array must be sorted before binary search can be used

Binary search mental model

Cut the search space in half each step

Binary search key variables

left, right, mid

Binary search loop condition

while (left <= right)

Binary search mid calculation snippet

int mid = left + (right - left) / 2;

Binary search comparison snippet

if (arr[mid] == target)

Binary search left move snippet

left = mid + 1;

Binary search right move snippet

right = mid - 1;

Binary search worst case time

O(log n)

Binary search best case time

O(1)

Binary search exam trap

Using binary search on an unsorted array

Selection sort mental model

Find the smallest element and move it to the front

Selection sort sorted region

Left side of the array grows sorted

Selection sort outer loop meaning

Controls the boundary of the sorted region

Selection sort min index snippet

int minIndex = i;

Selection sort comparison snippet

if (arr[j] < arr[minIndex]) minIndex = j;

Selection sort swap snippet

swap(arr[i], arr[minIndex]);

Selection sort swaps per pass

Exactly one swap per outer loop

Selection sort worst case time

O(n^2)

Selection sort best case time

O(n^2)

Selection sort exam trap

Assuming it becomes faster if array is already sorted

Insertion sort mental model

Sorting cards in your hand

Insertion sort sorted region

Everything to the left of the current index

Insertion sort outer loop start

i = 1 because first element is already sorted

Insertion sort swap-based while condition

while (j > 0 && arr[j] < arr[j-1])

Insertion sort swap snippet

swap(arr[j], arr[j-1]);

Insertion sort pointer movement snippet

j--;

Insertion sort best case time

O(n)

Insertion sort worst case time

O(n^2)

Insertion sort exam trap

Forgetting to move j after swap

Bubble sort mental model

Large values bubble to the right

Bubble sort sorted region

Right side of the array grows sorted

Bubble sort outer loop meaning

Reduces how far inner loop must go

Bubble sort neighbor comparison snippet

if (arr[j] > arr[j+1])

Bubble sort swap snippet

swap(arr[j], arr[j+1]);

Bubble sort optimized swap flag snippet

bool swapped = true;

Bubble sort early exit condition

sorted if no swaps occur in a pass

Bubble sort best case time

O(n) with swap check

Bubble sort worst case time

O(n^2)

Bubble sort exam trap

Claiming O(n) without swap optimization

Merge sort mental model

Split array until size 1, then merge back up

Merge sort base case snippet

if (left >= right) return;

Merge sort mid calculation snippet

int mid = left + (right - left) / 2;

Merge sort left recursion snippet

mergeSort(arr, left, mid);

Merge sort right recursion snippet

mergeSort(arr, mid + 1, right);

Merge sort merge call snippet

merge(arr, left, mid, right);

Merge sort worst case time

O(n log n)

Merge sort best case time

O(n log n)

Merge sort exam trap

Thinking merge sort is in-place

Tracing selection sort rule

Track minIndex each outer loop

Tracing insertion sort rule

Watch elements swap backward one position at a time

Tracing bubble sort rule

After each pass, the largest value is fixed at the end

Tracing merge sort rule