Re: fast stable sort

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.

While those algorithms are inherently stable,
you have to be careful when you code them
because they can also be coded as nonstable algorithms.

There is an example of a nonstable mergesort function
named "mergeSort", at:

http://www.azillionmonkeys.com/qed/sorttest.c

The function mergeSort, is not stable because
it uses a nonstable function named insertSort
to sort the small partitions.
insertSort uses a nonstable simple selection sort algorithm.

--
pete
.

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: Benchmarks
    ... fastest sort. ...  I prefer mergesort and data input in lists, ... mergesort is stable. ... _different_ algorithm (and probably has different average ...
    (comp.lang.c)
  • Re: Sorting algorithm problem
    ... >>You can do it with heap sort but it is much too complex. ... >>I developed this algorithm. ... It is a derivation of mergesort. ... Fun was better. ...
    (comp.theory)
  • Re: fast stable sort
    ... Which sorting methods are stable? ... There are in place stable versions of mergesort. ... Calling it folklore may be a bit of an overstatement; ... Finding the median in worst case time Ofalls in that category ...
    (comp.programming)