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.

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;