Problem Statement 
 MergeSort is a classical sorting algorithm following the divideandconquer paradigm. Sorting n elements, it has a worstcase
complexity of O(n*log(n)), which is optimal for sorting algorithms based on comparisons.
Basically, it sorts a list with more than one element the following way (a list containing only one element is always sorted):
 1. divide the list into two sublists of about equal size (divide)
 2. sort each of the two sublists (conquer)
 3. merge the two sorted sublists into one sorted list (combine)
A pro of MergeSort is that it is stable, i.e. elements with the same key value keep their relative order during sorting.
A con is that it is not inplace since it needs additional space for temporarily storing elements.
Given a int[] numbers, return the number of comparisons the MergeSort algorithm
(as described in pseudocode below) makes in order to sort that list. In this context, a single comparison takes two numbers x, y
(from the list to be sorted) and determines which of x < y, x = y and x > y holds.
List mergeSort(List a)
1. if size(a) <= 1, return a
2. split a into two sublists b and c
if size(a) = 2*k, b contains the first k elements of a, c the last k elements
if size(a) = 2*k+1, b contains the first k elements of a, c the last k+1 elements
3. List sb = mergeSort(b)
List sc = mergeSort(c)
4. return merge(sb, sc)
List merge(List b, List c)
1. create an empty list a
2. while both b and c are not empty, compare the first elements of b and c
first(b) < first(c): remove the first element of b and append it to the end of a
first(b) > first(c): remove the first element of c and append it to the end of a
first(b) = first(c): remove the first elements of b and c and append them to the end of a
3. if either b or c is not empty, append that nonempty list to the end of a
4. return a


Definition 
 Class:  MergeSort  Method:  howManyComparisons  Parameters:  int[]  Returns:  int  Method signature:  int howManyComparisons(int[] numbers)  (be sure your method is public) 




Notes 
  Be sure to exactly follow the algorithm as described, as a different implementation of MergeSort might lead to a different number of comparisons. 

Constraints 
  numbers contains between 0 and 50 elements, inclusive. 
  Each element of numbers is an int in its 'natural' (signed 32bit) range from (2^31) to (2^31)1. 

Examples 
0)  
  Returns: 4  {1, 2, 3, 4} is first split to {1, 2} and {3, 4}. {1, 2} is split to {1} and {2} and merging to {1, 2} takes one comparison. {3, 4} is split to {3} and {4} and merging to {3, 4} also takes one comparison. Merging {1, 2} and {3, 4} to {1, 2, 3, 4} takes two comparisons (first 1 is compared to 3 and then 2 is compared to 3). This makes a total of four comparisons. 


1)  
  Returns: 2  {2, 3, 2} is split to {2} and {3, 2}. {3, 2} is split and then merged to {2, 3} making one comparison. {2} and {2, 3} are merged to {2, 2, 3} also making one comparison, which totals to two comparisons made. 


2)  
 
3)  
 
4)  
 {2000000000,2000000000,0,0,0,2000000000,2000000000,0,0,0} 
 Returns: 19  
