"Can you compare common sorting algorithms such as bubble sort, insertion sort, merge sort, quicksort, and heap sort, and explain when you would choose each one based on time complexity, space usage, stability, and input characteristics?"
Sorting algorithms differ most obviously in their best, average, and worst-case running times. In interviews, you should distinguish algorithms with quadratic behavior like bubble and insertion sort from O(n log n) algorithms like merge sort, quicksort, and heap sort.
sorted_nums = sorted(nums) # Python's built-in sort hides these trade-offs internally
A stable sort preserves the relative order of elements with equal keys. Stability matters when sorting records by multiple fields, because a later stable sort can preserve the grouping established by an earlier one.
records = [(2, 'a'), (1, 'x'), (2, 'b')]
# A stable sort by first field keeps 'a' before 'b'
Some algorithms sort mostly in place, while others require additional memory proportional to the input size. This trade-off matters when memory is constrained or when predictable performance is more important than minimizing allocations.
Certain algorithms perform especially well on nearly sorted data, small arrays, or data with adversarial patterns. A strong answer explains not just asymptotic complexity, but how input shape changes practical performance.
Quicksort is often fast in practice but can degrade to O(n^2) with poor pivot choices, while merge sort and heap sort provide stronger worst-case guarantees. Choosing between them depends on whether you optimize for average speed, memory, or predictability.
