How Can I Replace StringList.Sort with a Stable Sort in Delphi?

Question

I'm doing a simple StringList.sort, but Delphi uses a QuickSort that is not a stable sort, meaning it may change the relative order of records with equal keys.

I need to use a stable sort. What would be the easiest way for me to implement this?

---

Mike W's answer might be the simplest way to do it without too much code change necessary.

Thanks, Mike.

Mating

Does this help? Easy way to add stable sorting to TList and TStringList (Not voting to close - just adding link for reference.) – Attica

@KenWhite - Thanks for that link. I missed it. But the answer there was to write your own sort. Surely there must be something somewhere that is easier than making 10,000 people who want to use a stable sort on StringList from having to figure out and write their own. – Mating

That's what TStringList.CustomSort is for - it's to allow you to write your own replacement for the built-in QuickSort. If you want something other than what's included, you need to write your own. :) You can always write your own TStringList descendant and implement your own Sort; it's virtual, so it can be overridden. – Attica

Yes, as @Mike W points out in his answer. – Mating

Where does he mention writing your own descendant? I can't find it. :) – Attica

No need to write a descendant. Just use CustomSort and define it. – Mating

@DavidHeffernan - Strange. It seems to work for me. That's exactly how I programmed and tested it. – Mating

@lkessler, if you try your compare function in my sample code you'll see that it's not stable when just comparing indexes like that. – Salientian

@MikeW: You're right. My simple test must just have got the right answer just randomly. ... Investigating further to see if I can still avoid the assignment of the objects. Your idea has got me on the right track, though, and at worst I can use it. – Mating

Answer 1

If you're not already using the Objects property of the string list a quick and dirty solution would be to store the original position in the objects property as an integer. You can then provide your own stable sort compare function that takes the original position into consideration. All you'd have to do in your own code is iterate the entire list assigning the objects property just before calling CustomSort:

function StableSortCompare(List: TStringList; Index1, Index2: Integer): Integer;
begin
  result := CompareStr(List[Index1], List[Index2]);
  if result = 0 then result := integer(List.Objects[Index1]) - integer(List.Objects[Index2]);
end;

procedure TSortTestForm.SortButtonClick(Sender: TObject);
var
  SL : TStringList;
  i : integer;
begin
  SL := TStringList.Create;
  try
    SL.AddObject('One', pointer(0));
    SL.AddObject('One', pointer(1));
    SL.AddObject('One', pointer(2));
    SL.AddObject('Two', pointer(3));
    SL.AddObject('Two', pointer(4));
    SL.AddObject('One', pointer(5));
    SL.AddObject('One', pointer(6));
    SL.AddObject('One', pointer(7));
    // SL.Sort; // Try instead of custom sort to see difference
    SL.CustomSort(StableSortCompare);
    for i := 0 to SL.Count-1 do begin
      Memo1.Lines.Add(Format('Text: %s Orig Pos: %d', [SL[i], integer(SL.Objects[i])]));
    end;
  finally
    SL.Free;
  end;
end;

Salientian

That's actually not that bad. But why not in the StableSortCompare routine just use: "if result = 0 then result := Index1 < Index 2". Won't that properly keep the lower index equal key lower than the higher index equal key? It that's tcorrect, then you wouldn't have to assign the objects. – Mating

@Mating that doesn't compile, for a start, but I see what you mean. It won't work though. There's nothing to stop two items getting swapped en route to the final destination. – Bartolomeo

I don't think so. The QuickSort may well swap two different strings before trying to compare two that are the same. At that point you've lost the original index which is what's important for stability. – Salientian

@DavidHeffernan - I tried to edit it, but my 5 minutes ran out. Correction going into my chosen answer (in my question) - working on that now. – Mating

What if latter expression will return 0 too? – Estimable

@user that would mean that the sort algo was comparing an item with itself – Bartolomeo

If you're not using the object pointer, why would stable sorting matter? – Iceland

@Svein - true, in which case you'd need add the original index to whatever the object pointer references – Salientian