Name a comparison-based sorting algorithm with average time complexity O(n log n).

• A. Bubble sort
• B. Merge sort
• C. Insertion sort
• D. Counting sort

Answer: (B)

Sorting by comparing elements and using a strategy that splits the data and merges results yields efficient performance. Merge sort does exactly that: it splits the list in two, recursively sorts each half, and then merges the two sorted halves by repeatedly comparing the smallest remaining elements. This divide-and-conquer process leads to a recurrence T(n) = 2T(n/2) + O(n), which solves to O(n log n) on average. Among the options, this is the one that uses comparisons and achieves the desired O(n log n) average time. The other common sorts either run in O(n^2) on average because they swap or shift many elements, or (in the case of counting sort) aren’t based on comparisons and have a time complexity of O(n + k), depending on the range of input values.