### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: LCLProc MergeSort seems not stable  (Read 1291 times)

#### apeoperaio

• Sr. Member
• Posts: 260
##### LCLProc MergeSort seems not stable
« on: January 30, 2023, 09:58:54 am »
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  [Select][+][-]
1.   procedure SmallSort(StartPos, EndPos: PtrInt);
2.   // use insertion sort for small lists
3.   var
4.     i: PtrInt;
5.     Best: PtrInt;
6.     j: PtrInt;
7.     Item: Pointer;
8.   begin
9.     for i:=StartPos to EndPos-1 do begin
10.       Best:=i;
11.       for j:=i+1 to EndPos do
12.         if OnCompare(List[Best],List[j])>0 then
13.           Best:=j;
14.       if Best>i then begin
15.         Item:=List[i];
16.         List[i]:=List[Best];
17.         List[Best]:=Item;
18.       end;
19.     end;
20.   end;
21.

Would be the following implementation stable?

Code: Pascal  [Select][+][-]
1.   procedure SmallSort(StartPos, EndPos: PtrInt);
2.   // use insertion sort for small lists
3.   var
4.     i: PtrInt;
5.     Best: PtrInt;
6.     j: PtrInt;
7.     Item: Pointer;
8.   begin
9.     for i:=StartPos to EndPos-1 do begin
10.       Best:=i;
11.       for j:=i+1 to EndPos do
12.         if OnCompare(List[Best],List[j])>0 then
13.           Best:=j;
14.       if Best>i then begin
15.         Item:=List[Best];
16.         List.Delete(Best);
17.         List.Insert(i, Item);
18.       end;
19.     end;
20.   end;
21.

• Hero Member
• Posts: 12933
##### Re: LCLProc MergeSort seems not stable
« Reply #1 on: January 30, 2023, 11:23:35 am »
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  [Select][+][-]
1. program SortOfAnIssue;
2. {\$mode objfpc}{\$H+}
3. uses types;
4.
5. procedure MergeSort(var A: TIntegerDynArray; const Buf: TIntegerDynArray; const Left, Right: Integer);inline;overload;
6. var
7.   Center, I, J, K: Integer;
8. begin
9.   if Right - Left > 1 then
10.   begin
11.     Center := (Left + Right) div 2;
12.     MergeSort(A, Buf, Left, Center);
13.     MergeSort(A, Buf, Center, Right);
14.     for I := Left to Center - 1 do
15.       Buf[I] := A[I];
16.     I := Left;
17.     J := Center;
18.     K := Left;
19.     while I < Center  do
20.     begin
21.       if J >= Right then
22.         A[K] := Buf[I]
23.       else if Buf[I] < A[J] then
24.         A[K] := Buf[I]
25.       else
26.         A[K] := A[J];
27.       Inc(I);
28.       Inc(K);
29.       if J < Right then
30.         Inc(J);
31.     end;
32.   end
33.   else if Right - Left = 1 then  // adjust here, can be anything small that suits you.
34.   begin
35.     // Insertion Sort for small sizes
36.     J := Left;
37.     while (J > 0) and (A[J-1] > A[J]) do
38.     begin
39.       I := A[J-1];
40.       A[J-1] := A[J];
41.       A[J] := I;
42.       Dec(J);
43.     end;
44.   end;
45. end;
46.
48. begin
49.   MergeSort(A, A, 0, Length(A));
50. end;
51.
52. var
53.  Items:TIntegerDynArray = { objfpc } (707,707,101);  // mode delphi is: [707,707,101]; // square brackets
54.  i:integer;
55. begin
56.   mergesort(Items);
57.   for i in items do writeln(i);
58. 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.
« Last Edit: January 30, 2023, 12:15:24 pm by Thaddy »
In memory of Gordon Moore  (January 3, 1929 – March 24, 2023) Just double the heaven every two years from now.

#### apeoperaio

• Sr. Member
• Posts: 260
##### Re: LCLProc MergeSort seems not stable
« Reply #2 on: January 30, 2023, 03:23:00 pm »
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

• Hero Member
• Posts: 3156
• POKE 54296,15
##### Re: LCLProc MergeSort seems not stable
« Reply #3 on: January 30, 2023, 04:59:01 pm »
Devil is in details. It depends what algorithm does with the same values.
Code: Pascal  [Select][+][-]
1.  if OnCompare(List[Best],List[j])>0 then
I.e. change from ">" to "  >=" can make it stable.

But of course, it depends how is "OnCompare" implemented.
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

• Hero Member
• Posts: 12933
##### Re: LCLProc MergeSort seems not stable
« Reply #4 on: January 30, 2023, 05:30:39 pm »
Indeed, if lcl implements right to left evaluation that is is the cause.
(But my code shows the two conditions to be met for a stable sort even if mixing insertion and Merge, which is technically a hybrid)

Anyway: the lcl implementation looks broken.
In memory of Gordon Moore  (January 3, 1929 – March 24, 2023) Just double the heaven every two years from now.

#### Blaazen

• Hero Member
• Posts: 3156
• POKE 54296,15
##### Re: LCLProc MergeSort seems not stable
« Reply #5 on: January 30, 2023, 05:33:31 pm »
Guys, you mystified me!

It's not InsertionSort, it is SelectionSort. SelectionSort - by wiki - can be implemented as a stable but usually is not.

https://en.wikipedia.org/wiki/Selection_sort

BTW: Why the link replaces h t t p with ** ?
« Last Edit: January 30, 2023, 05:40:29 pm by Blaazen »
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

#### Fred vS

• Hero Member
• Posts: 2983
##### Re: LCLProc MergeSort seems not stable
« Reply #6 on: January 30, 2023, 06:03:46 pm »
I use Lazarus 2.2.0 32/64 and FPC 3.2.2 32/64 on Debian 11 64 bit, Windows 10, Windows 7 32/64, Windows XP 32,  FreeBSD 64.
Widgetset: fpGUI, MSEgui, Win32, GTK2, Qt.

https://github.com/fredvs
https://gitlab.com/fredvs
https://codeberg.org/fredvs

#### Blaazen

• Hero Member
• Posts: 3156
• POKE 54296,15
##### Re: LCLProc MergeSort seems not stable
« Reply #7 on: January 30, 2023, 08:35:19 pm »
To make the original Selection Sort stable is needed to replace:
Code: Pascal  [Select][+][-]
1.  if Best>i then begin
2.         Item:=List[i];
3.         List[i]:=List[Best];
4.         List[Best]:=Item;
5.       end;

with
Code: Pascal  [Select][+][-]
1.   if Best>i then begin
2.         Item:=List[Best];
3.         system.Move(List[i], List[i+1], (Best-i)*sizeOf(Item));
4.         List[i]:=Item;
5.       end;
i.e. shift all items instead of just swap two. Of course, List must be continuous memory (array).
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

#### apeoperaio

• Sr. Member
• Posts: 260
##### Re: LCLProc MergeSort seems not stable
« Reply #8 on: February 08, 2023, 12:26:02 pm »
@Blaaze, I tried your code but if I use it I got the error:
lclproc.pas(1150,39) Error: Can't take the address of constant expressions

on:
Code: Pascal  [Select][+][-]
1. system.Move(List[i], List[i+1], (Best-i)*sizeOf(Item));

• Hero Member
• Posts: 12933
##### Re: LCLProc MergeSort seems not stable
« Reply #9 on: February 08, 2023, 01:52:45 pm »
That's why I wrote a stable sort for both cases. See above.
In memory of Gordon Moore  (January 3, 1929 – March 24, 2023) Just double the heaven every two years from now.

#### Blaazen

• Hero Member
• Posts: 3156
• POKE 54296,15
##### Re: LCLProc MergeSort seems not stable
« Reply #10 on: February 08, 2023, 05:10:19 pm »
system.Move can't work here. List is TStrings where you access items via abstract getters and setters. i.e. it's not continuous memory.
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

#### apeoperaio

• Sr. Member
• Posts: 260
##### Re: LCLProc MergeSort seems not stable
« Reply #11 on: February 13, 2023, 09:30:47 am »
That's why I wrote a stable sort for both cases. See above.

Thanks!