Searching & Sorting

Linear and binary search, then every classic sort from bubble to quick sort.

1. 3.1Linear SearchCheck every item from left to right until you find the key or run out. Works on any array, sorted or not, but costs O(n).easy
2. 3.2Binary SearchOn a sorted array, check the middle, then throw away the half that cannot contain the key. Each step halves the problem, so it takes O(log n).medium
3. 3.3Selection SortFind the smallest remaining item and swap it to the front. Repeat. Simple, at most n − 1 swaps, but always O(n²) comparisons.easy
4. 3.4Bubble SortCompare neighbours and swap them if they are out of order. After each pass the biggest remaining item has "bubbled" to the end.easy
5. 3.5Insertion SortGrow a sorted part on the left by inserting each new item into its correct place, like sorting cards in your hand. Fast on nearly sorted data.easy
6. 3.6Pointer SortWhen records are big, don't move them. Sort an array of pointers (or indices) to the records instead, and only small addresses get swapped.medium
7. 3.7Shell SortInsertion sort on items a gap apart, with the gap shrinking to 1. Far-away items move in big jumps, so the final insertion sort has little work left.medium
8. 3.8Merge SortSplit the array in half, sort each half recursively, then merge the two sorted halves. Always O(n log n), stable, but needs O(n) extra space.medium
9. 3.9Quick SortPick a pivot, partition so smaller items go left and bigger items go right, then sort each side recursively. Average O(n log n), worst O(n²).hard