can someone explain the difference between quicksort and mergesort to me?
they both seem identical, with the only difference between them that mergesort divides exactly at the middle element, whereas quicksort attempts to pick the 'true' median element.
also, from what i've read, it is 'expected' that mergesort keep on dividing till there are n lists of 1 element, whereas quicksort alternatively CAN divide until its sublists reach a certain length(or a certain recursive height has been reached), at which point another [linear(?)] sorting algorithm would be used
Difference between quicksort and mergesort
Page 1 of 14 Replies  16753 Views  Last Post: 04 July 2008  05:03 PM
#3
Re: Difference between quicksort and mergesort
Posted 03 July 2008  10:18 PM
The Architect 2.0, on 3 Jul, 2008  09:09 PM, said:
can someone explain the difference between quicksort and mergesort to me?
they both seem identical, with the only difference between them that mergesort divides exactly at the middle element, whereas quicksort attempts to pick the 'true' median element.
also, from what i've read, it is 'expected' that mergesort keep on dividing till there are n lists of 1 element, whereas quicksort alternatively CAN divide until its sublists reach a certain length(or a certain recursive height has been reached), at which point another [linear(?)] sorting algorithm would be used
they both seem identical, with the only difference between them that mergesort divides exactly at the middle element, whereas quicksort attempts to pick the 'true' median element.
also, from what i've read, it is 'expected' that mergesort keep on dividing till there are n lists of 1 element, whereas quicksort alternatively CAN divide until its sublists reach a certain length(or a certain recursive height has been reached), at which point another [linear(?)] sorting algorithm would be used
Mergesort is bottomup, while quicksort is topdown. Even though you might see the term topdown associated with a particular implementation of mergesort, a merge sort works on that if you have two ordered lists, combining them to get a larger sorted list involves a simple comparison of the head element of each list, until each sublist has been processed. Since a merge requires the lists to be ordered, merges must be applied to sublists of increasing size.
Quicksort is applied on the entire list first, then each sublist (opposite of merge sort). If I have element X, and I place all elements less than X before it, and everything else after, then X will be in it's final position at the end of the sort. After all, nothing on the one side could ever be put on the other side, as they're all less than X.
There's no reason why you couldn't apply a linear sort in combination with a merge sort. It's just that there's little incentive to do so. With quicksort, optimal performance is obtained by selecting the optimal partition element (a.k.a. X). If X is always the least or greatest element in the list, then performance becomes more like O(N**2). There are ways around it, and one of them is the introsort algorithm (a quicksort that changes to a heapsort when the recursion depth exceeds a threshold).
#4
Re: Difference between quicksort and mergesort
Posted 03 July 2008  10:35 PM
ah, i understand now.
quicksort does all the comparisons/sorting on the 'tophalf'(when lists are beign divided) of the algorithm, whereas mergesort does all the sorting on the 'bottomhalf'(when the lists are being merged).
thanks alot.
quicksort does all the comparisons/sorting on the 'tophalf'(when lists are beign divided) of the algorithm, whereas mergesort does all the sorting on the 'bottomhalf'(when the lists are being merged).
thanks alot.
#5
Re: Difference between quicksort and mergesort
Posted 04 July 2008  01:12 PM
If you'd like to see the time comparison between merge and quicksort, take a look at this
http://www.onlyconn...gi?SortingClass
quicksort is a bit faster than merge sort when dealing with large data
http://www.onlyconn...gi?SortingClass
quicksort is a bit faster than merge sort when dealing with large data
#6
Re: Difference between quicksort and mergesort
Posted 04 July 2008  05:03 PM
I'd also add that, in general, merge sorting requires more memory.
Page 1 of 1
