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.

Answer 2

This question is rather old, but here goes my answer for future readers: I also needed this recently and adapted the implementation found in the book "The Tomes of Delphi Algorithms and Data Structures" by Julian Bucknall. Implementation for TList, TObjectList and descendant classes. It works with Delphi 2009 to XE7 and probably other versions as well: http://alexandrecmachado.blogspot.com.br/2015/02/merge-sort-for-delphi.html