Forum > LCL

LCLProc MergeSort seems not stable

(1/3) > >>

apeoperaio:
I was looking for a stable sorting algorithm and I came up to the MergeSort algotithm implemented in LCLProc.
Wikipedia states that most implementations of merge sort produce a stable sort.
Anyway the MergeSort implementation seems not stable.
Let's suppose we  have a list of three items:
'707' (idx 0)
'707' (idx 1)
'101' (idx 2)

Looking at the MergeSort implementation the final results will be:
'101' (idx 2)
'707' (idx 1)
'707' (idx 0)

That's not stable.

The original implementation is:

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---  procedure SmallSort(StartPos, EndPos: PtrInt);  // use insertion sort for small lists  var    i: PtrInt;    Best: PtrInt;    j: PtrInt;    Item: Pointer;  begin    for i:=StartPos to EndPos-1 do begin      Best:=i;      for j:=i+1 to EndPos do        if OnCompare(List[Best],List[j])>0 then          Best:=j;      if Best>i then begin        Item:=List[i];        List[i]:=List[Best];        List[Best]:=Item;      end;    end;  end;
Would be the following implementation stable?

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---  procedure SmallSort(StartPos, EndPos: PtrInt);  // use insertion sort for small lists  var    i: PtrInt;    Best: PtrInt;    j: PtrInt;    Item: Pointer;  begin    for i:=StartPos to EndPos-1 do begin      Best:=i;      for j:=i+1 to EndPos do        if OnCompare(List[Best],List[j])>0 then          Best:=j;      if Best>i then begin        Item:=List[Best];        List.Delete(Best);        List.Insert(i, Item);      end;    end;  end;

Compare with the two Rosetta code entries?
rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Pascal

Note that with both examples and the size of your array, you are not testing mergesort, but insertion sort.
Anyway, I found it fun, so I wrote a version from scratch that can be proven stable:
--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---program SortOfAnIssue;{\$mode objfpc}{\$H+}uses types; procedure MergeSort(var A: TIntegerDynArray; const Buf: TIntegerDynArray; const Left, Right: Integer);inline;overload;var  Center, I, J, K: Integer;begin  if Right - Left > 1 then  begin    Center := (Left + Right) div 2;    MergeSort(A, Buf, Left, Center);    MergeSort(A, Buf, Center, Right);    for I := Left to Center - 1 do      Buf[I] := A[I];    I := Left;    J := Center;    K := Left;    while I < Center  do    begin      if J >= Right then        A[K] := Buf[I]      else if Buf[I] < A[J] then        A[K] := Buf[I]      else        A[K] := A[J];      Inc(I);      Inc(K);      if J < Right then        Inc(J);    end;  end  else if Right - Left = 1 then  // adjust here, can be anything small that suits you.  begin    // Insertion Sort for small sizes    J := Left;    while (J > 0) and (A[J-1] > A[J]) do    begin      I := A[J-1];      A[J-1] := A[J];      A[J] := I;      Dec(J);    end;  end;end; procedure MergeSort(var A: TIntegerDynArray);inline;overload;begin  MergeSort(A, A, 0, Length(A));end; var Items:TIntegerDynArray = { objfpc } (707,707,101);  // mode delphi is: [707,707,101]; // square brackets i:integer;begin  mergesort(Items);  for i in items do writeln(i);end.That is, keeping the rosetta code entries in mind and hopefully some prior knowledge left-overs.
There is still room for improvement: fast fingers, slow mind.
May also be slow speed, but point was to prove stability.

apeoperaio:
Thank you. I will look at the code.
Anyway, my list has more than 3 items. It was just an example to show that the SmallSort procedure inside the LCLProc mergesort seems to break the stability.

Blaazen:
Devil is in details. It depends what algorithm does with the same values.

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} --- if OnCompare(List[Best],List[j])>0 thenI.e. change from ">" to "  >=" can make it stable.

But of course, it depends how is "OnCompare" implemented.