Sorting Algorithms comparison in NAV AL with Visual Studio Code

In order to exercise in the new NAV Modern Development Environment I thought to implement a comparison of two sorting algorithms directly in Visual Studio Code AL Language: Insertion Sort and Merge Sort.

Most of the sorting examples over the internet are using arrays, but the issue with arrays is they have fixed length that needs to be declared upfront. Of course I didn’t like this even if it is just an example with educational purpose. Or someone maybe will use it also for a real situation, we’ll see.

As I said also in a previous post, the AL Language has now a built in List wrapper. The problem is that this List does not have a Sort method:

Before I started to write this post I implemented the Insertion Sort using temporary tables because I was sure that the List has it’s own Sort method so it wouldn’t be fun to create something that already exists and performs much better. But it seems it’s not the case. How did Microsoft miss this one ?

So I created a new AL extension:

For this project, first I created a Setup Page:

Here, there are 2 options of running the sorting algorithms:
1) CreateInMemory: The Random numbers that will be sorted are created at run time, in memory: this is fine for small tests, but in case of more than 10000 numbers, it takes too long time to populate the List/Temp Table with random numbers.
2) CopyFromDatabase: The Random Numbers are first Created in the database in a table called “Random Numbers” which looks like this in SQL Server:

Then, when we run the sorting algorithms we just copy the random numbers from the database instead of generating them at runtime. This way, we can test the sorting algorithms on much larger sets of numbers. It will take some time just once (when we populate the table). For example for 1.000.000 random numbers it took about 4-5 minutes for this system:

It takes so long because my method of creating these random numbers creates unique random numbers. For example if you want the numbers from 1 to 1000 but mixed up. Or you can have 1000 unique mixed up numbers picked up from numbers between 1 to 3000. For everything up to 1.000.000 it’s ok, but for more it is pretty slow. If you have a faster way of doing this please write a comment 🙂

In this setup page you can see also other fields:
– No of Random Numbers in Memory: specifies the number of random numbers created in memory in an AL List or Nav Temporary table.
– Random Selection Max Number Memory: ex: if you want to generate in memory 5 random numbers selected from numbers between 1 to 10 you will specify here 10; if you want 5 number from 1 to 5 you specify here 5 etc.
– No Of Random Nos Real Table: specifies the number of random numbers created and inserted into database by function “Populate Random Numbers Table”
– Random Selection Max Number Table: similar to “Random Selection Max Number Memory” but for the numbers inserted into the database.
– Maximum Values Displayed in Message: after you sort numbers, the program displays the initial numbers (unsorted) and resulted numbers (sorted) in a message. In case you have a lot of numbers the message cannot display because the text is too long. By filling this field the program will display only the numbers until the value specified in it. Ex: if you sorted 100.000 numbers and this value is 300 the program displays first 300 numbers and text: “and 99.700 more”.

If you want to use the option RunMode = CopyFromDatabase you first have to populate the Random Numbers Table. When you select this option I implemented a check: in case the Random Numbers table is empty, it will ask if you want to populate it. If you select Yes, it will run the same script as action “Populate Random Number”.

field(9;RunMode; Option)
        {
           OptionMembers = CopyFromDatabase,CreateInMemory;
        
        trigger OnValidate();
           var
            RandomNos : Record RandomNumbers;
            RandomNosMgt : Codeunit RandomNosMgt;
            RandomTabEmptylbl : label '%1 is empty. Do you want to run job to populate it ?';
           begin
                If RunMode = RunMode::CopyFromDatabase then
                    If RandomNos.IsEmpty then
                        If Confirm(StrSubstNo(RandomTabEmptylbl,RandomNos.TableCaption)) and (NoOfRandomNosRealTable > 0)  then
                            RandomNosMgt.FillRealRecWithRandomNumbers(NoOfRandomNosRealTable,RandomSelectionMaxNumberTable);
           end;
        }

If you use action “Populate Random Numbers” and you already have data in the Random Numbers table, it will delete all existing data and create a new set of numbers.

–> The logic of generating the Random numbers is the same for the table/temp table and list. The code that populates the table is this one:

procedure FillRealRecWithRandomNumbers(NumberOfValuesWanted : Integer; RandomSelectionMaxNumber : Integer)
    var
    i : integer;
    ListOfInt : List Of [Integer];
    RandomNumbers : Record RandomNumbers;
    intprimarykey : Integer;
    randomposition : integer;
    RemainedRandomNumbers : Integer;
    ProgressWindow : Dialog;
    begin
        If NOT RandomNumbers.IsEmpty then
            Exit; //values already were added at a previous run

        //add values to List
        for i := 1 to RandomSelectionMaxNumber do
                ListOfInt.Add(i);
            
        ProgressWindow.Open('Creating Random Nos @1@@@@@@@@@');
        RemainedRandomNumbers := RandomSelectionMaxNumber;
        //select random values from List and add to RandomNumbers. Then delete the added number from ListOfInt
        for i := 1 to NumberOfValuesWanted do begin
            ProgressWindow.UPDATE(1,ROUND(i /  NumberOfValuesWanted * 10000,1));
            
            randomposition := random(RemainedRandomNumbers); //get a random position

            //add value to RandomNumbers
            RandomNumbers.PrimaryKey := intprimarykey;
            RandomNumbers.RandomNumber := ListOfInt.Get(randomposition);
            RandomNumbers.Insert;
            intprimarykey += 1;
        
            //detele value from ListOfInt to have only unique random numbers
            ListOfInt.RemoveAt(randomposition);

            RemainedRandomNumbers -= 1;
            If RemainedRandomNumbers = 0 THEN //in case someone inputs more wanted values than the RandomNumbers
                break;
        end;
        ProgressWindow.Close;
    end;

So, I hope I explained clear enough how I designed this small app. Now, I will explain how I implemented the Insertion Sort using the AL List, then Nav temporary tables and I will leave for the end the Merge Sort. (start with an easy thing and finish with a more complicated one).

The logic of the Insertion Sort algorithm is very simple and nice to my opinion. I created the bellow example to explain it:

Now let’s see the implementations in AL

1) Insertion Sort Using AL List:

codeunit 50101 InsertionSortList
{
    trigger OnRun();
    var
    RandomNumbersList : List of [Integer];
    InitialRandomValuesString : Text;
    ResultedSortedValuesString : Text;
    MessageText : TextConst ENU = 'Initial Numbers:\\%1\\Sorted Numbers:\\%2';
    StartTime : DateTime;
    EndTime : DateTime;
    ExecutionTime : DateTime;
    RandomNosMgt : Codeunit RandomNosMgt;
    RandomNosSetup : Record RandomNosSetup;
    begin
        RandomNosSetup.Get;
        If RandomNosSetup.RunMode = RandomNosSetup.RunMode::CreateInMemory Then
            RandomNosMgt.FillRandomNumbersList(RandomNumbersList,
                RandomNosSetup.NoOfRandomNosInMemory,RandomNosSetup.RandomSelectionMaxNumberMemory)
        Else
            RandomNosMgt.FillRandomNumbersListFromRealTable(RandomNumbersList);

        RandomNosMgt.CreateStringWihValuesList(RandomNumbersList,InitialRandomValuesString); //generate string for message
           
        StartTime := CurrentDateTime;
        InsertionSort(RandomNumbersList);
        EndTime := CurrentDateTime;
        
        RandomNosMgt.CreateStringWihValuesList(RandomNumbersList,ResultedSortedValuesString); //generate string for message

        Message('Executed in %1',EndTime-StartTime);
        Message(MessageText,InitialRandomValuesString,ResultedSortedValuesString);
    end;
    
    var
    local procedure InsertionSort(RandomNumbersList : List of [Integer]);
    var
    NumberOfElements : integer ; i : Integer; j : integer; CurrentElement : Integer;
    ProgressWindow : Dialog;
    begin
       ProgressWindow.Open('Sorting Random Nos @1@@@@@@@@@');
       NumberOfElements := RandomNumbersList.Count;
       for i := 2 to NumberOfElements do begin
           ProgressWindow.UPDATE(1,ROUND(i /  NumberOfElements * 10000,1));
           CurrentElement := RandomNumbersList.Get(i);
           j := i-1;

           while RandomNumbersList.Get(j) > CurrentElement do begin
               RandomNumbersList.Set(j+1,RandomNumbersList.get(j));
               j -= 1;
               if j = 0 then
                break;
           end;
           RandomNumbersList.Set(j+1,CurrentElement);
       end;
       ProgressWindow.Close;
    end;
}

2) Insertion Sort Using Nav temporary table (pretty slow for a lot of random numbers because of the next statements. Just as exercise. If you have a better way of doing it please share it):

local procedure InsertionSort(var tempRandomNumbers : Record RandomNumbers temporary; NosCount : Integer);
    var
    CurrKey : Integer; CurrValue : Integer; IntToMoveRight : Integer; StepsMovedLeft : Integer;
    swapped : Boolean; ProgressWindow : Dialog; i: integer;
    begin
        ProgressWindow.Open('Sorting Random Nos @1@@@@@@@@@');
        If tempRandomNumbers.FindSet then begin
            tempRandomNumbers.Next(1); //start with second record
            repeat
                i+=1;
                ProgressWindow.UPDATE(1,ROUND(i /  NosCount * 10000,1));
                swapped := false;
                CurrKey := tempRandomNumbers.PrimaryKey;
                CurrValue := tempRandomNumbers.RandomNumber;
                //move to the right any numbers greater than the current one
                StepsMovedLeft := tempRandomNumbers.Next(-1);
                while (StepsMovedLeft < 0) AND (tempRandomNumbers.RandomNumber > CurrValue) do begin
                    IntToMoveRight := tempRandomNumbers.RandomNumber;
                    tempRandomNumbers.Next(1);
                    tempRandomNumbers.RandomNumber := IntToMoveRight;
                    tempRandomNumbers.Modify;
                    tempRandomNumbers.Next(-1);
                    StepsMovedLeft := tempRandomNumbers.Next(-1);
                    swapped := true;
                end;
                // if items where moved to right, 
                if swapped then begin
                    If StepsMovedLeft < 0 then
                        tempRandomNumbers.Next(1); 
                    tempRandomNumbers.RandomNumber := CurrValue;
                    tempRandomNumbers.Modify;
                end;
  
                tempRandomNumbers.Get(CurrKey); //go back to initial record
            until tempRandomNumbers.Next = 0;
        end;
        ProgressWindow.Close;
    end;   

3) Now, the merge sort. The logic of this algorithm is best explained in this link.
This is much, much faster than Insertion Sort and other simple algorithms: for example it can sort millions of random numbers in just few seconds while the insertion sort needs minutes for 100.000 random numbers.

Let’s see the implementation of Merge Sort in Visual Studio Code using the AL List:

local procedure MergeSort(RandomNosList : List of [Integer]; leftStart : integer; rightEnd : Integer);
    var
        middle : integer;
    begin
        if leftStart >= rightEnd then
            Exit;

         middle := round(((leftStart-1 + rightEnd) / 2),1,'>');
         MergeSort(RandomNosList,leftStart,middle);
         MergeSort(RandomNosList,middle+1,rightEnd);
         MergeHalves(RandomNosList,leftStart,rightEnd);
    end;

    local procedure MergeHalves(RandomNosList : List of [Integer]; leftStart : integer; rightEnd : Integer);
    var
        i : Integer; j : integer; k : Integer; leftEnd : integer; rightStart : Integer; x : integer; y:integer;
        tempList : List of [Integer];
    begin
        leftEnd := Round(((rightEnd + leftStart - 1) / 2),1,'>');
        rightStart := leftEnd + 1;
        i := leftStart; j := leftEnd + 1; k := leftStart;

        //create temp sorted list
        while (i <= leftEnd) and (j <= rightEnd)  do begin
            If RandomNosList.Get(i) < RandomNosList.Get(j) then begin
                tempList.Add(RandomNosList.Get(i));
                i+=1;
            end else 
            begin
                tempList.Add(RandomNosList.Get(j));
                j+=1;
            end;
            k+=1;
        end;

        while i < leftEnd + 1 do begin
            tempList.Add(RandomNosList.Get(i)); //add remaing elements from left list
            i += 1;
        end;

        while j < rightEnd + 1 do begin
            tempList.Add(RandomNosList.Get(j)); //add remaing elements from right list
            j += 1;
        end;

        //copy sorted elements to main list
        y := leftStart;
        for x := 1 to tempList.Count do begin
            RandomNosList.Set(y,tempList.Get(x));
            y+=1;
        end;
    end;

–> Performance Comparison:

No. Of Random Nos.	Insertion sort temp table	Insertion Sort List	Merge Sort List
1.000	4 seconds	110 miliseconds	10 miliseconds
5.000	1 minute 15 seconds	2 seconds	110 miliseconds
10.000	5 minutes 29 seconds	8 seconds	120 miliseconds
50.000	N/A	2 minutes 55 seconds	500 miliseconds
100.000	N/A	11 minutes 30 seconds	1 second
250.000	N/A	N/A	2.5 seconds
500.000	N/A	N/A	5 seconds
1.000.000	N/A	N/A	11 seconds
5.000.000	N/A	N/A	1 minute

–> Quick presentation video of how to use the sorting app:

*I used the Windows client because in the current Web Client there is a limitation and the Progress Dialog is not displayed correctly.

Conclusions:
– The insertion sort performs good when there are not a lot of numbers to be sorted or it is used for numbers that are already “almost” sorted. For example in case of adding new numbers to a previusly sorted list and then sorting the list again. For random numbers it works fine for 1000-3000 numbers, but in case of more than 10000 it takes some time. For this kind of situations there are better sorting algorithms, for example the Merge Sort.
– When possible use the AL List. It can be much faster compared to temporary tables for a lot of situations. Depending, of course, on your algorithm that uses it.
– If you need to sort an AL List, you can use the Merge Sort from this project until Microsoft implements the sorting method for this object in AL.

Next Steps:
– It would be interesting to create the QuickSort algorithm in NAV as well, in order to compare it with the Merge Sort, but I didn’t have time to do also that. Maybe will do it in future or if someone else does it, please share.

I hope you enjoyed this exercise with sorting algorithms, you can download the app from below GitHub link, install in NAV and play with it. Folder “SortingMethods“:
https://github.com/andreilungu/NAV_AL