Sorting Notes

Bubble Sort Implementation

Bubble sort explained simply: repeatedly swap adjacent out-of-order items, with an early-exit optimisation. O(n^2) time, stable, in Python, Java and C...

Data Structures

Selection Sort Implementation

Selection sort explained: repeatedly pick the smallest remaining element and place it next. O(n^2) time with the fewest swaps, in Python, Java and C++...

Data Structures

Insertion Sort Implementation

Insertion sort explained: build a sorted prefix by inserting each element into place. O(n^2) worst but O(n) on nearly sorted data; stable, in Python...

Data Structures

Merge Sort Implementation

Merge sort explained: divide the array in half, sort each half, then merge. Guaranteed O(n log n), stable, with Python, Java and C++ code.

Data Structures

Quick Sort Implementation

Quick sort explained: partition around a pivot and recurse. O(n log n) average, in-place, with the Lomuto partition in Python, Java and C++.

Data Structures

Heap Sort Implementation

Heap sort explained: build a max-heap, then repeatedly move the max to the end. O(n log n) worst case, in-place, with Python, Java and C++ code.

Data Structures

Counting Sort Implementation

Counting sort explained: tally occurrences of each value, then rebuild the array. O(n + k) time for small integer ranges, in Python, Java and C++.

Data Structures

Radix Sort Implementation

Radix sort explained: sort integers digit by digit using a stable counting sort per digit. O(d(n + k)) time, in Python, Java and C++.

Data Structures

Bucket Sort Implementation

Bucket sort explained: scatter elements into buckets by range, sort each bucket, then concatenate. O(n) average for uniform data, in Python, Java and...

Data Structures

Sort an Array (Built-in vs Custom Comparator)

Sort an Array (LeetCode 912): how to use built-in sorts and custom comparators in Python, Java and C++, including ascending, descending and key-based...

Data Structures

Merge Intervals Using Sorting

Merge Intervals (LeetCode 56): sort by start, then merge overlapping intervals in one pass. O(n log n), with Python, Java and C++ code.

Data Structures

Largest Number Formed from an Array

Largest Number (LeetCode 179): sort numbers by a custom pairwise rule (a+b vs b+a) to form the biggest concatenation. O(n log n), Python/Java/C++.