Time Complexity of Sorting Algorithms

Question: Discuss the time complexities of common sorting algorithms (e.g., bubble sort, insertion sort, merge sort, quick sort, heap sort).

Answer framing: Bubble/insertion/selection sort: O(n^2) average and worst case (O(n) best case for insertion sort on nearly-sorted data). Merge sort: O(n log n) in all cases, O(n) extra space. Quick sort: O(n log n) average, O(n^2) worst case (poor pivot choices), O(log n) space for the recursion stack. Heap sort: O(n log n) in all cases, O(1) extra space (in-place) but not stable. Discuss stability, in-place vs extra-space trade-offs, and when each is preferred (e.g., merge sort for stable sorts / linked lists, quicksort for average-case in-place performance, heap sort for guaranteed O(n log n) with O(1) space).