Sorting Algos

Bubble sort

Whats sorted first: LARGEST element (At the end)

Steps:
Compare adjacent elements
Swap if theyre in the wrong order
“Bubble” the largest element to the end
Repeat for remaining unsorted portion

Selection sort

Whats sorted first: SMALLEST element (at the beginning)

Steps:
Find the minimum element in unsorted portion
Swap it with the first unsorted position
Move sorted/unsorted boundary (iterate)
Repeat

Insertion sort

Whats sorted first: FIRST element

Steps:
Start with first element (considered sorted)
Take next element and insert it into correct position insorted portion
Shift elements as needed
Repeat for all elements

Quicksort

Whats sorted first: THE PIVOT

Steps:
Choose a pivot element
Partition: move elements left and right of the pivot (L → < pivot, R → > Pivot)
Pivot is in the final position
Recursively do the sort left and right

Merge sort

Whats sorted first: NONE

Steps:
Divide array in half recursively until single elements
Merge sorted halves back together
Repeat until fully sorted

Bubble sort time complexity

Best Case: O(n)
Average Case: O(n²)
Worst Case: O(n²)

Selection sort time complexity

Best Case: O(n²)
Average Case: O(n²)
Worst Case: O(n²)

Insertion Sort time complexity

Insert
Best Case: O(n)
Average Case: O(n²)
Worst Case: O(n²)

Quicksort time complexity

Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n²)

Merge sort time complexity

Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)

Bubble sort properties

Selection sort properties

Insertion sort properties

Quicksort properties

Merge sort properties

Stable

Stable sort preserves relative order of elements with equal keys

10 2 10 → 2 10 10

In-place

Sorting algo that uses O(1) space → If you use an array of size 3 then it would use an extra array of size 3

Internal

The data is stored in ram → small enough to run in ram vs external which uses othe rdrives

Adaptive

Checks if its sorted or nearly sorted firs

Radix sort time complexity

O(dn)