4 Replies - 17092 Views - Last Post: 04 July 2008 - 05:03 PM Rate Topic: -----

#1 The Architect 2.0  Icon User is offline

  • D.I.C Regular

Reputation: 37
  • View blog
  • Posts: 351
  • Joined: 22-May 08

Difference between quicksort and mergesort

Posted 03 July 2008 - 09:09 PM

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

Is This A Good Question/Topic? 0
  • +

#3 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: Difference between quicksort and mergesort

Posted 03 July 2008 - 10:18 PM

View PostThe 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


Mergesort is bottom-up, while quick-sort is top-down. Even though you might see the term top-down 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).
Was This Post Helpful? 1

#4 The Architect 2.0  Icon User is offline

  • D.I.C Regular

Reputation: 37
  • View blog
  • Posts: 351
  • Joined: 22-May 08

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 'top-half'(when lists are beign divided) of the algorithm, whereas mergesort does all the sorting on the 'bottom-half'(when the lists are being merged).

thanks alot.
Was This Post Helpful? 0
  • +
  • -

#5 ibaraku  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 190
  • Joined: 12-May 07

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.only-conn...gi?SortingClass
quicksort is a bit faster than merge sort when dealing with large data
Was This Post Helpful? 1

#6 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3106
  • View blog
  • Posts: 19,145
  • Joined: 14-September 07

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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1