Sorting algorithms

Sorting choices depend on input size, stability, memory, key range, and whether the data is almost sorted. Bubble and selection sort are mainly teaching tools; insertion sort is good for tiny or nearly sorted data; merge sort is stable with extra memory; quicksort is fast on average; heap sort controls memory; counting sort needs a bounded key range.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers may not ask you to code every sort, but they expect you to compare complexity, stability, and why a language built-in sort may be preferable in product code.

Common pitfalls: Quicksort worst case can be O(n squared). Counting sort is not comparison sort and can waste memory. Stable ordering matters when equal keys carry secondary data.

Checklist:

• Mention time and space.
• State stability.
• Check key range.
• Prefer built-in sort unless implementation is the task.