05 Complete Script

# Source URL: https://dev.epicgames.com/documentation/en-us/uefn/sorting-algorithms-in-verse
# Local doc:  epic-docs/documentation/en-us/uefn/sorting-algorithms-in-verse.md
# Section:    Complete Script
# 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.