Problem Statement
Which sorting algorithm has the best average-case time complexity?
Explanation
Merge Sort has the best average-case time complexity of O of n log n among the options given. Bubble Sort and Insertion Sort both have O of n squared average and worst-case complexity, making them inefficient for large datasets.
Merge Sort consistently achieves O of n log n by dividing the array into halves recursively and merging them back in sorted order. This divide-and-conquer approach guarantees logarithmic depth with linear work at each level. Quick Sort also has O of n log n average case but can degrade to O of n squared in worst case. Merge Sort's guaranteed performance makes it reliable for all inputs.
Code Solution
SolutionRead Only
// Time Complexity Comparison:
// Bubble Sort - O(n^2)
// Nested loops, compares adjacent elements
for (i = 0; i < n; i++)
for (j = 0; j < n-1; j++)
// Compare and swap
// Insertion Sort - O(n^2)
// For each element, find correct position
for (i = 1; i < n; i++)
// Shift elements - O(n)
// Merge Sort - O(n log n)
// Divide: log n levels
// Conquer: O(n) work per level
mergeSort(arr, 0, n-1)
divide into halves // log n times
merge sorted halves // O(n) per level
// For n=1000:
// Bubble/Insertion: ~1,000,000 operations
// Merge Sort: ~10,000 operations