Insertion 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.

• ✗Comparing neighbours (gap 1) in every pass, which is just insertion sort.
• ✗Forgetting that the last pass must use gap = 1, or the array may not be sorted.
• ✗Claiming it is stable. Jumps over a gap can reorder equal keys.

Pick 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²).

• ✗Recursing on (lo, p) instead of (lo, p − 1). The pivot is already in place.
• ✗Forgetting the final swap(a[i + 1], a[hi]) that puts the pivot in place.
• ✗Saying quick sort is always O(n log n).

Split 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.

• ✗Forgetting to copy the leftover items after one half runs out.
• ✗Using < instead of <= in merge, which breaks stability.
• ✗Base case lo > hi only. A single item (lo == hi) must also stop the recursion.

Build a max-heap in the array, then repeatedly swap the root (the largest item) to the end and sift down. O(n log n) in every case, in-place.

• ✗Using 1-based formulas (2i, 2i+1) with a 0-based array. With 0-based it is 2i+1 and 2i+2.
• ✗Starting the build loop at i = 0 instead of n/2 − 1, going down to 0.
• ✗Calling heapify on the whole array instead of the shrinking heap size end.

A hash function turns a key into an array index, so search is O(1) on average. Collisions, separate chaining, linear probing and the load factor.

• ✗With linear probing, stopping a search at a slot holding a different key. Only an empty slot means "not found".
• ✗Forgetting to wrap around with % M when probing.
• ✗Claiming hashing is always O(1). The worst case is O(n).