# Difference between quicksort and mergesort

Page 1 of 1

## 4 Replies - 20331 Views - Last Post: 04 July 2008 - 05:03 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=56633&amp;s=7a87065906120f27f20c446b1f52a442&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 The Architect 2.0

• D.I.C Regular

Reputation: 37
• 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

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

## 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

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).

### #4 The Architect 2.0

• D.I.C Regular

Reputation: 37
• 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.

### #5 ibaraku

Reputation: 3
• 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

### #6 KYA

• Wubba lubba dub dub!

Reputation: 3186
• Posts: 19,211
• 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.