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)

Sorting algorithms can be judged by how fast they run on average and whether they preserve the relative order of equal elements. Quicksort achieves an average-case time of O(n log n) because it partitions the array around a pivot and recursively sorts the pieces; when the pivot splits the data roughly in half, the recurrence T(n) ≈ 2T(n/2) + cn leads to the n log n growth on average. But it isn’t guaranteed to be stable, since during partitioning equal elements can be rearranged in ways that change their original order. That combination—average-case O(n log n) and lack of guaranteed stability—makes quicksort the best match here. (For contrast, merge sort is stable and also O(n log n) on average, bubble sort is O(n^2) on average, and heap sort is O(n log n) but not stable in its typical form.)

Sorting algorithms can be judged by how fast they run on average and whether they preserve the relative order of equal elements. Quicksort achieves an average-case time of O(n log n) because it partitions the array around a pivot and recursively sorts the pieces; when the pivot splits the data roughly in half, the recurrence T(n) ≈ 2T(n/2) + cn leads to the n log n growth on average. But it isn’t guaranteed to be stable, since during partitioning equal elements can be rearranged in ways that change their original order. That combination—average-case O(n log n) and lack of guaranteed stability—makes quicksort the best match here. (For contrast, merge sort is stable and also O(n log n) on average, bubble sort is O(n^2) on average, and heap sort is O(n log n) but not stable in its typical form.)