Re: fast stable sort

On Thu, 13 Nov 2008 05:19:53 -0500, pete <pfiland@xxxxxxxxxxxxxx>
wrote:

subramanian100in@xxxxxxxxx, India wrote:
I am practicing C programming at home. The C standard library function
qsort() as per the C standard document, need not be stable. So I want
to know the following.

Which sorting methods are stable ?
Among the stable sorting methods, which method is both stable and
fastest ?

For small arrays, insertion sort is usually fastest.
For large arrays, merge sort is usually fastest,
but it is not an in place sorting algorithm.

Caveat: There are in place stable versions of mergesort. IIRC
the best known is about three times slower than a version that
uses extra memory.

"Merge sort is not in place" is one of those bits of comp sci
folklore.



Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • Re: fast stable sort
    ... Which sorting methods are stable? ... insertion sort is usually fastest. ... There are in place stable versions of mergesort. ... Calling it folklore may be a bit of an overstatement; ...
    (comp.programming)
  • Re: fast stable sort
    ... Which sorting methods are stable? ... insertion sort is usually fastest. ... There are in place stable versions of mergesort. ...
    (comp.programming)
  • Re: fast stable sort
    ... Which sorting methods are stable? ... For large arrays, merge sort is usually fastest, ... There is an example of a nonstable mergesort function ... insertSort uses a nonstable simple selection sort algorithm. ...
    (comp.programming)
  • Re: New technology, old idea.... why not?
    ... Are we there then on sorting data? ... sort using pairwise comparisons and you have no exploitable ... so the sorting methods don't need information ... The tallest strand now stands higher than all ...
    (comp.lang.java.help)
  • Re: fast stable sort
    ... For small arrays, insertion sort is usually fastest. ...
    (comp.programming)