Merge sort is so modified that for array sizes below 11, instead of recursive Merge sort, the array is sorted using Bubble sort. Will there be any good and bad cases now? Give an example of each case if you think so; if not, argue why.
My thought process:
I understand that the worst-case complexity of bubble sort remains the same as its average-case complexity, but since it is not specified as to how to categorize the "worst case" (only according to its worst-case complexity or even considering least comparisons), I also considered having the least number of comparisons.
For Merge sort, I understand that the worst case will arise when the elements in the merged array are selected alternatively from the two sub-arrays.
So, for an array size of, say 24, I produced the following array -
24, 20, 16, 12, 8, 4, 23, 19, 15, 11, 7, 3, 22, 18, 14, 10, 6, 2, 21, 17, 13, 9, 5, 1
In the first iteration of Merge sort, there will be two sub-arrays of length 12 each. Since this is more than 11, Merge sort is recursively called again.
At some point, we will have four sub-arrays of length 6. At this point Bubble sort will be applied to each of them and they will be recursively joined by Merge sort. The four sub-arrays will be -
[24, 20, 16, 12, 8, 4], [23, 19, 15, 11, 7, 3], [22, 18, 14, 10, 6, 2], [21, 17, 13, 9, 5, 1]
Now each of these present a worst-case for Bubble sort, since all have their elements in descending order. Now lets say the first two arrays are sorted using Bubble sort and merged, they will present a worst case for Merge sort as during the merge operation each element will be alternatively chosen from the two sub-arrays. Similarly, the last two sub-arrays are sorted using Bubble sort and merged.
Is this array a correct example of the worst case of the above problem? Or am I wrong in deriving this conclusion?