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?

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?

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.

You could probably also keep your shell sort and use the current position index as a secondary key if two elements compare equal.

I will study mergesort. Thanks