Merge Sort

1616,165 Views

Report

• 
  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)