03 Implementing Merge Sort

# 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:    Implementing Merge Sort
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