Which sorting algorithm has an average-case time complexity of O(n log n) and is not guaranteed to be stable?

Which sorting algorithm has an average-case time complexity of O(n log n) and is not guaranteed to be stable?

• A. Merge sort
• B. Bubble sort
• C. Heap sort
• D. Quicksort

Answer: (D)

Average-case performance for QuickSort comes from partitioning the array around a chosen pivot. Each pass touches all elements, and the recursion depth is about log n on average, so the total work scales roughly as n log n. Stability, meaning keeping the relative order of equal elements, isn’t guaranteed with the standard QuickSort because elements can be moved across partitions during swapping, so equal keys may end up in a different order. While there are stable variants, the usual QuickSort implementation is not stable. Merge sort, by contrast, is also O(n log n) on average and is stable, which is why it doesn’t fit the “not guaranteed to be stable” part. Bubble sort is O(n^2) on average, and heap sort is O(n log n) but not stable in its typical form, though the classic emphasis here is QuickSort’s combination of good average performance and lack of guaranteed stability.