Which sorting algorithm is commonly not stable but has an average time complexity of O(n log n)?

Which sorting algorithm is commonly not stable but has an average time complexity of O(n log n)?

• A. Insertion sort
• B. Merge sort
• C. Quicksort
• D. Selection sort

Answer: (C)

Two concepts are being tested here: stability of a sort and its average running time. Stability means that if two items have equal keys, their relative order remains the same after sorting. Quicksort achieves fast average performance by partitioning the array around a chosen pivot and recursively sorting the partitions. This partitioning often swaps elements across the pivot, which can change the relative order of equal elements, so it is not stable in the usual implementation. At the same time, its average-case time is O(n log n) because each level of recursion processes all n elements and the problem size halves on average, leading to about log n levels of work. To contrast, insertion sort, while stable, has an average and worst-case time of O(n^2); merge sort is O(n log n) and stable; and selection sort is O(n^2) and generally unstable, but it does not achieve O(n log n) on average. So the algorithm that fits both criteria—unstable by default and average time O(n log n)—is quicksort.

Two concepts are being tested here: stability of a sort and its average running time. Stability means that if two items have equal keys, their relative order remains the same after sorting. Quicksort achieves fast average performance by partitioning the array around a chosen pivot and recursively sorting the partitions. This partitioning often swaps elements across the pivot, which can change the relative order of equal elements, so it is not stable in the usual implementation. At the same time, its average-case time is O(n log n) because each level of recursion processes all n elements and the problem size halves on average, leading to about log n levels of work.

To contrast, insertion sort, while stable, has an average and worst-case time of O(n^2); merge sort is O(n log n) and stable; and selection sort is O(n^2) and generally unstable, but it does not achieve O(n log n) on average. So the algorithm that fits both criteria—unstable by default and average time O(n log n)—is quicksort.