Some Type Of MergesortComputer Science Level 4
Merge sort is an efficient sorting algorithm that uses a divide-and-conquer approach to order elements in an array. A standard Mergesort algorithm runs in a guaranteed \(O(n\log n)\) time, which is significantly faster than the average and worst-case running times of several other sorting algorithms.
The worst case of merge sort will be the one, where the merge sort will have to do maximum number of comparisons. Given a list \(L\) containing integers 1 to 8 inclusive, how many permutations of \(L\) are there such that the merge sort runs in the worst case?