Easy way to add stable sorting to TList and TStringList

Question

I use TList/TObjectList and TStringList (with associated objects) for a multitude of tasks, either as-is, or as basis for more complex structures. While the sort functionality is usually good enough, I sometimes need to do a stable sort, and both lists use quicksort.

What's the easiest way to implement stable sorting for TList and/or TStringList? Do I have to write my own sorting routine, or can it be done by using some clever trick with TStringListSortCompare/TListSortCompare?

Answer 1

You'll have to write your own sorting routine.

You can read the current QuickSort implementation, and write your own stable version (e.g. a Merge sort or any other stable variant).

Some tricks:

• If you are sure that an index is < Count, you can use the fast pointer array (TList.List[]) instead of slower Items[] or GetItem(): sub-method calling and range checking slow down the execution;
• The comparison function is most of the time the speed bottleneck of the search - so take care of this part;
• If you need speed, use a real profiler over real (e.g. random) data - but make it right before making it fast;
• Start from an existing implementation of the sort;
• To minimize stack space, you may use a temporary record to store and share variables among recursive calls.