Problem statement:

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?

  • $\begingroup$ This would be better presented as a question, followed by your own answer, which is permitted. Or at least it should be stated so that answers can be more than yes and no, for example by sketching answer rather than being very detailed.. You could ask for points you might have forgotten. BTW 12 is more than 11, not less. $\endgroup$ – babou Apr 12 '15 at 7:57
  • 1
    $\begingroup$ @babou I think the format of this is better suited as a question, since answers should only contain material you are convinced is right. $\endgroup$ – Raphael Apr 12 '15 at 9:19
  • $\begingroup$ I think you are on the right track: Mergesort does not do any reordering "downwards" (unlike Quicksort) so it's comparatively easy to come up with bad inputs for this algorithm. Your approach looks fine to me; now generalize it to $n$-element lists! (Hint: $n = 10k$ may be a useful assumption.) And come up with the "best" case, too! $\endgroup$ – Raphael Apr 12 '15 at 9:22
  • $\begingroup$ Note that exchanging one sorting algorithm for another for lists of constantly-bounded size won't change the $\Theta$-runtime of the algorithm; it will change constant factors, though. They probably don't want you to rigorously analyse this. It's interesting, though: for instance, finding the (theoretically) optimal cut-off length between Quicksort and Insertion Sort is kind of standard. $\endgroup$ – Raphael Apr 12 '15 at 9:22
  • 1
    $\begingroup$ One example of constant size can never form a worst-/best-case argument. You need an infinite set of examples (of growing size) in order to argue for an asymptotic property. So even if your example is a step in right direction, the instructor would be correct in not awarding full credit. $\endgroup$ – Raphael Apr 13 '15 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.