Implement
the “mergeSort”
method as described in the reference program below (will be discussed in
class):
The merge
sort algorithm is typically solved as two methods:
a) The “split” method: Divides the array in half
during each call. O (log n)
b) The “mergeSort”
method: Merges the two sorted sub-arrays
into a single, sorted array. O (n)
Analysis:
· Running Time: Since
the Step b) is nested within Step a), the total running time of the Merge Sort
algorithm is O (n log n).
· Space Requirements: Since we are using an additional array (of input size) in the mergeSort method,
the space requirements of the Merge Sort algorithm are O (n).
