QuickSort for sorting part Mergesort?
Ques: Mergesort divides a list of numbers into two halves and calls itself recursively on both of them. Instead can you perform quicksort on the left half and mergesort on the right half? If yes, show how it will sort the following list of numbers by showing every step. If no, explain why you cannot.
Iam supposed to sort a list of numbers using mergesort. Where the left half is to be sorted using a quicksort ?
I figured it out. Ans:Yes,we can
Yes, you can do this. The basic idea behind mergesort is the following:
From the perspective of correctness, it doesn't actually matter how you sort the lists generated in part (2). All that matters is that those lists get sorted. A typical implementation of mergesort does step (2) by recursively applying itself to the left and right halves, but there's no fundamental reason you have to do this. (In fact, in some optimized versions of mergesort, you specifically don't do this and instead switch to an algorithm like insertion sort when the arrays get sufficiently small).
In your case, you are correct that using quicksort on the left and mergesort on the right would still produce a sorted sequence. However, the way in which it would work would look quite different from what you're describing. What would end up happening is something like this: the first half of the array would get quicksorted (because you quicksort the left half), then you'd recursively sort the right half. The first half of that would get quicksorted, then you'd recursively sort the right half. The first half of that would get quicksorted, etc. Overall this would look something like this:
This would be a pretty cool-looking sort, but doing it by hand would be a total pain. You might be better off writing a program that just does this and showing all the intermediate steps. :-)
No, you cannot do it. At least if you still want to call it "merge sort". The most fundamental difference between merge sort and quick sort is that the first is a stable algorithm, ie equally ordered elements keep their relative positions unaltered after sorting. This is important in many scenarios. If you sort the second half using quick sort, the relative position of equal elements can (and very likely will) change. The resulting set will not preserve stability so it can't be still considered merge sort.
By the way, previous answer is correct regarding insertion sort used as the last step of merge sort. Most efficient merge sort implementations will use something like insertion sort when the number of elements is small. Insertion sort is also stable, that's why it can be done without breaking merge sort stability.
链接地址: http://www.djcxy.com/p/31586.html