TopCoder problem "MergeSort" used in SRM 151 (Division I Level Two , Division II Level Three)



Problem Statement

    MergeSort is a classical sorting algorithm following the divide-and-conquer paradigm. Sorting n elements, it has a worst-case 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 in-place 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 non-empty 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 32-bit) range from -(2^31) to (2^31)-1.
 

Examples

0)
    
{1, 2, 3, 4}
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)
    
{2, 3, 2}
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)
    
{-17}
Returns: 0
3)
    
{}
Returns: 0
4)
    
{-2000000000,2000000000,0,0,0,-2000000000,2000000000,0,0,0}
Returns: 19

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1705

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4560&pm=1705

Writer:

Wernie

Testers:

lbackstrom , brett1479

Problem categories:

Simulation, Sorting