Sorting algorithms

Bubble sort (idea)

Repeatedly compare adjacent items and swap if out of order; after each pass, the largest unsorted item “bubbles” to the end.

Bubble sort (one pass)

Scan left→right doing neighbor comparisons/swaps; after the pass, the last position is correct.

Bubble sort (stop early)

If a full pass makes 0 swaps, the list is already sorted—stop.

Bubble sort (time)

Worst/avg: O(n^2). Best (already sorted + early-stop): O(n).

Bubble sort (space)

O(1) extra space (in-place).

Bubble sort (stable?)

Yes—equal elements keep their relative order (with standard adjacent-swap version).

Selection sort (idea)

Repeatedly select the smallest element from the unsorted portion and swap it into the next position.

Selection sort (one pass)

Find minimum in indices i..end, swap with index i.

Selection sort (time)

Best/avg/worst: O(n^2) comparisons (always scans remaining items).

Selection sort (space)

O(1) extra space (in-place).

Selection sort (stable?)

Not necessarily (swapping the min can reorder equals).

Insertion sort (idea)

Build a sorted left portion by taking the next element and inserting it into the correct position (shifting larger items right).

Insertion sort (key operation)

Shift items right until the insertion spot is found, then place the key there.

Insertion sort (time)

Worst/avg: O(n^2). Best (already sorted): O(n).

Insertion sort (space)

O(1) extra space (in-place).

Insertion sort (stable?)

Yes—commonly stable (shifts preserve order of equals).

Merge sort (idea)

Divide the list into halves until single elements, then merge sorted halves back together.

Merge sort (merge step)

Combine two sorted lists by repeatedly taking the smaller front element.

Merge sort (time)

Best/avg/worst: O(n log n).

Merge sort (space)

O(n) extra space (typical array/list implementation).

Merge sort (stable?)

Yes—stable if merge prefers left element on ties.

Merge sort (pattern)

Divide-and-conquer: split → solve subproblems → combine.

Quick sort (idea)

Pick a pivot, partition into < pivot and > pivot, then recursively sort partitions.

Quick sort (partition)

Rearrangement step that moves items so left side < pivot and right side > pivot (pivot ends in its final spot).

Quick sort (time)

Avg: O(n log n). Worst (bad pivots): O(n^2). Best: O(n log n).

Quick sort (space)

In-place partitioning is O(1) extra array space, but recursion stack is typically O(log n) avg (O(n) worst).

Quick sort (stable?)

Not stable in standard in-place versions.

Quick sort (pivot choice)

Better pivot choices (random/median-of-three) reduce chance of worst-case partitions.

Binary search (requirement)

Array/list must be sorted (ascending or descending consistently).

Binary search (idea)

Check the middle element; eliminate half the remaining range each step.

Binary search (mid formula)

mid = (low + high) // 2 (integer division).

Binary search (update rules)

If target < A[mid], set high = mid-1; if target > A[mid], set low = mid+1; if equal, found.

Binary search (time)

O(log n) comparisons.

Binary search (space)

O(1) extra space iterative; O(log n) recursion stack if recursive.

Binary search (not found)

If low > high, the search range is empty → target is not in the list.

In-place (definition)

Uses only constant extra memory (O(1)) beyond the input storage.

Stable sort (definition)

Equal keys keep the same relative order they had in the original input.

Pass (sorting)

A single full sweep/iteration of the main outer loop that places at least one element into its final position.

Comparison sort (definition)

Sorting method that determines order solely by comparing elements (bubble/selection/insertion/merge/quick).

When to use insertion sort

Great for small lists or nearly-sorted data; low overhead.

When to use merge sort

Great when you need guaranteed O(n log n) time and stability; common for linked lists/external sorting.

When to use quick sort

Fast in practice for arrays with good pivots; common default in many libraries (variants).

Bubble vs selection (main difference)

Bubble swaps neighbors repeatedly; Selection finds a min and swaps once per pass.

Insertion vs selection (main difference)

Insertion shifts to insert one key into sorted left side; Selection picks the min and swaps.

Merge vs quick (main difference)

Merge split+merge needs extra memory but guaranteed O(n log n); Quick partitions in-place but worst-case O(n^2).