Re: Mergesort Vs Quicksort

Richard Heathfield <rjh@xxxxxxxxxxxxxxx> writes:

adintimes@xxxxxxxxx said:

Hi all,

Though in terms of average and best case complexity, both merge sort
and quick sort are the same, it is generally observed that the most
popular method of sorting is quicksort. Also if we consider the worst
case, quick sort is even worse compared to merge sort. Of course with
the right selection of pivot we can always avoid the worst case from
happening.

Any thoughts on why quicksort is preferred over merge sort.

Perhaps because it's slightly more obvious.

Here's the shortest explanation I have been able to come up with for
Quicksort, in the few seconds for which I was trying:

"Pick an arbitrary member of a data set, put all lesser members to its left
and the rest to its right, and the arbitrary member is now in its correct
sorted position, with unsorted data sets to its left and right. Recurse
into any data set having more than one member."

Mergesort:

"Break the array into a number of data sets. Mergesort each data set having
more than one member [or, at your preference, if it has fewer than N
members for low N, do some other kind of sort on it instead, eg insertion
sort or Shell sort]. Then, until none of those original data sets have any
members, compare the first members of all the (remaining) data sets and
take the member with the lowest key and move it to the output data set
(removing it from the original, thus causing that data set to have a new
first member)."

You loaded the dice! If we can assume that merging two sorted lists
into one, and partitioning a list into those elements <= x and those >
x are both adequate high-level descriptions of the key parts then they
are both equally simple to describe. They both have an extra bit --
mergesort has a "split in two" and quicksort has a "join the bits
together" -- but neither needs much detail at this level.

Maybe someone can improve on those a bit, but Quicksort sounds a lot easier
to do, doesn't it? And in fact it *is* easier to write working Quicksort
code than to write working Mergesort code.

It is much easier to implement quicksort of we start with an array,
but given a list I can't see why there would be much difference.

--
Ben.
.

Relevant Pages

  • Re: Mergesort Vs Quicksort
    ... quick sort is even worse compared to merge sort. ... Quicksort, in the few seconds for which I was trying: ... "Pick an arbitrary member of a data set, put all lesser members to its left ...
    (comp.programming)
  • Re: Mergesort Vs Quicksort
    ... Though in terms of average and best case complexity, both merge sort ... Any thoughts on why quicksort is preferred over merge sort. ... "Pick an arbitrary member of a data set, put all lesser members to its left ...
    (comp.programming)
  • Re: Mergesort Vs Quicksort
    ... Quicksort, in the few seconds for which I was trying: ... "Pick an arbitrary member of a data set, put all lesser members to its left and the rest to its right, ... evenly on both sides of the pivot. ...
    (comp.programming)
  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: Quicksort
    ... version, unless, of course you can afford order N stack space. ... fully recursive form to the semi recursive form of quicksort by ... If the compiler does tail recursion elimination, ... quicksort, in the average case, is one of the fastest sort algos. ...
    (comp.programming)