I need a sorting routine to use with my Virtual ListView.
Now I'm using shellsort but it has a problem: it is not stable.
I don't know if the term "stable" is the correct one. If I sort first the column A and then the column B, the elements that have the same value in the column B should be sorted according to the previous column A order

The first algorithm I used was selection sort (stable algorithm) but it does (N^2)/2 comparison. My listview has about 5000 rows and contains only strings. I have no problems with exchanges, because I change pointers, but I need a low number of comparison.

Shellsort, with knuth sequence (h = 3*h +1) is very good (less than N^ 3/2 comparison) but it is not stable.

Can someone tell me a fast stable algorithm?
Posted on 2004-07-10 08:13:55 by greenant
Merge sort is stable (depending on the implementation), and is used in some C++ STL implementations of stable_sort.

You could probably also keep your shell sort and use the current position index as a secondary key if two elements compare equal.
Posted on 2004-07-10 09:32:47 by Jibz
I will study mergesort. Thanks
Posted on 2004-07-10 09:36:18 by greenant