Merge Sort Algorithm

Module — 2 files

These files compile together (same module folder).

SortingAlgorithms.verse

SortingAlgorithms := module:
    # A divide-and-conquer sorting algorithm that divides an array into two, sorts each divided array, and then merges the arrays together.
    # This is a recursive implementation, where the function calls itself to merge sort the divided arrays.
    # The base case (the condition to stop the recursion) is the array has only one element.
    # This is a generic implementation using parametric types, so you can provide your own type and your own comparison function as arguments.
    MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        Length:int = Array.Length

        if:
            Length > 1 # Verify there is more than one element in the array, otherwise we've reached the base case.
            Mid:int = Floor(Length / 2) # Get the middle index of the array.
            Left:[]t = Array.Slice[0, Mid] # Split the array in half. This keeps elements from the beginning to Mid - 1 index.
            Right:[]t = Array.Slice[Mid] # Split the array in half. This keeps elements from Mid index to the end of the array.
        then:
            # Call MergeSort on the left half of the array.
            LeftSorted:[]t = MergeSort(Left, Compare)
            # Call MergeSort on the right half of the array.
            RightSorted:[]t = MergeSort(Right, Compare)

            # Combine the two arrays and return the result.
            Merge(LeftSorted, RightSorted, Compare)
        else:
            # Return the array passed in because we've reached the base case.
            Array

    # A helper function for MergeSort that combines the divided arrays in an order based on the Compare function.
    Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        var LeftIndex:int = 0
        var RightIndex:int = 0
        var MergedArray:[]t = array{}
        
        # Loop through all the elements in the arrays to add them to the MergedArray variable.
        loop:
            if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
                # Check the element in the left half array with the element in the right half array.
                # Uses the Compare function passed in as an argument
                if (Compare[LeftElement, RightElement]):
                    set MergedArray += array{LeftElement}
                    set LeftIndex += 1
                else:
                    set MergedArray += array{RightElement}
                    set RightIndex += 1
            else:
                # We've added all of the elements from one the arrays at this point.
                # Now check which array still has elements to merge in and add all remaining elements.
                if (LeftIndex >= Left.Length):
                    option{set MergedArray += Right.Slice[RightIndex]}
                else:
                    option{set MergedArray += Left.Slice[LeftIndex]}

                # Exit out of the loop because we've finished adding all elements.
                break
            
        # Return the merged array.
        MergedArray

test_sorting.verse

using { /Fortnite.com/Devices }
using { /UnrealEngine.com/Temporary/Diagnostics }
using { /Verse.org/Simulation }
using { /Verse.org/Random }

test_sorting_log_channel<public> := class(log_channel):
 
# A project-wide "Logger" to print messages from functions that are not in a class with a log.
# The non-Logger Print is <no_rollback>, so it can't be used in a <transacts> function.
ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
    Logger := log{Channel := test_sorting_log_channel}
    Logger.Print(Message, ?Level := Level)

# A Verse-authored creative device that can be placed in a level
test_sorting := class(creative_device):

    # Runs when the device is started in a running game
    OnBegin<override>()<suspends>:void=
        Sleep(0.0)

        var ArrayLength:int = GetRandomInt(10, 100)
        Test1ExpectedIntArray:[]int = for (Count := 0..GetRandomInt(10, 100)):
            Count
        Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)

        set ArrayLength = GetRandomInt(10, 100)
        Test2ExpectedIntArray:[]int = for (Count := 0..ArrayLength):
            ArrayLength - Count
        Test2ActualIntArray:[]int = Shuffle(Test2ExpectedIntArray)

        Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
        Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)

        set ArrayLength = GetRandomInt(10, 100)
        Test4ExpectedPlayerStats:[]player_stats = for (Count := 0..ArrayLength):
            player_stats:
                Wins := ArrayLength - Count
                RoundsPlayed := GetRandomInt(Count, Count * 30)
        Test4ActualPlayerStats:[]player_stats = Shuffle(Test4ExpectedPlayerStats)

        if:
            RunArrayTest["Integer array in order from smallest to largest", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
            RunArrayTest["Integer array in order from largest to smallest", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
            RunArrayTest["Integer array in order from smallest to largest with repeats", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
            RunArrayTest["Player stats array in order from largest # wins to smallest", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
        then:
            ProjectLog("All tests passed.")
        else:
            ProjectLog("One or more tests failed.")

RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=
    ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

    ProjectLog("Testing: {Description}")
    ProjectLog("Actual: {ArrayToString(ActualArray)}")
    ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
    ProjectLog("Result: {ArrayToString(ResultArray)}")

    for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
        Result = Expected

IntArrayToString(Array:[]int)<transacts>:string=
    var ConvertedToString:string = "["
    
    for(Index -> Element : Array):
        set ConvertedToString += "{Element}"
        if (Index < Array.Length - 1):
            set ConvertedToString += ", "
        
    set ConvertedToString += "]"

PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
    var ConvertedToString:string = "["
    
    for(Index -> Element : Array):
        set ConvertedToString += "{Element.Wins}"
        if (Index < Array.Length - 1):
            set ConvertedToString += ", "
        
    set ConvertedToString += "]"

IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
    Left < Right

IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
    Left > Right

player_stats := class<unique>:
    Wins:int = 0
    RoundsPlayed:int = 0

IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
    Left.Wins < Right.Wins
    Left

IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
    Left.Wins > Right.Wins
    Left

Copy-paste each file above is always free.

Merge Sort Algorithm

Comments