Statistics

Problem Statement for "MergeSort"

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

  1. {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.

  2. {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.

  3. {-17}

    Returns: 0

  4. {}

    Returns: 0

  5. {-20}

    Returns: 0

  6. {7, 7}

    Returns: 1

  7. {4, 3}

    Returns: 1

  8. {3, 4}

    Returns: 1

  9. {1, 2, 3}

    Returns: 2

  10. {1, 3, 2}

    Returns: 2

  11. {2, 1, 3}

    Returns: 3

  12. {2, 3, 1}

    Returns: 3

  13. {3, 1, 2}

    Returns: 3

  14. {3, 2, 1}

    Returns: 3

  15. {1, 1, 2}

    Returns: 2

  16. {1, 2, 1}

    Returns: 2

  17. {2, 1, 1}

    Returns: 3

  18. {1, 1, 1}

    Returns: 2

  19. {1, 2, 3, 4, 5, 6, 7}

    Returns: 9

  20. {7, 6, 5, 4, 3, 2, 1}

    Returns: 11

  21. {47, 36}

    Returns: 1

  22. {16, 30, 46}

    Returns: 2

  23. {36, 26, 33, 14}

    Returns: 5

  24. {23, 18, 37, 37, 5}

    Returns: 7

  25. {20, 25, 1, 41, 42, 23}

    Returns: 10

  26. {25, 39, 0, 37, 30, 12, 47}

    Returns: 14

  27. {41, 32, 33, 30, 31, 19, 48, 14}

    Returns: 17

  28. {17, 34, 42, 1, 1, 15, 21, 38, 2}

    Returns: 19

  29. {29, 11, 29, 30, 2, 23, 5, 30, 13, 6}

    Returns: 24

  30. {17, 45, 20, 16, 36, 4, 49, 18, 38, 21, 16}

    Returns: 27

  31. {2, 38, 3, 44, 41, 4, 11, 15, 44, 15, 44, 5}

    Returns: 28

  32. {44, 26, 8, 20, 34, 38, 35, 40, 7, 30, 12, 24, 17}

    Returns: 35

  33. {17, 25, 37, 5, 46, 4, 9, 37, 9, 3, 28, 15, 14, 43}

    Returns: 38

  34. {9, 29, 39, 15, 25, 18, 25, 45, 2, 15, 32, 44, 24, 13, 6}

    Returns: 40

  35. {0, 32, 23, 26, 19, 30, 24, 25, 39, 11, 34, 42, 42, 49, 8, 37}

    Returns: 42

  36. {11, 39, 29, 26, 17, 47, 3, 14, 49, 18, 47, 43, 42, 10, 49, 45, 44}

    Returns: 49

  37. {25, 21, 13, 5, 47, 41, 45, 9, 25, 39, 3, 27, 0, 40, 38, 41, 21, 16}

    Returns: 51

  38. {8, 18, 19, 23, 19, 39, 22, 14, 33, 34, 16, 28, 28, 41, 49, 43, 48, 49, 34}

    Returns: 52

  39. {-1437091263, 1501670972, 716373032, 1116631301, -732859106, -1539331901, -1281417393, -1167652725, 688931660, -1441761044, 688931660, -1126886511, -569924439, 253060386, 193039816, -372592555, 929210903, -183615805, 552793671, 668036989}

    Returns: 62

  40. {1479524095, 1479524095, 1082981104, 513056665, 766117051, 959156867, 586564313, 513056665, 754211028, 839080859, -534601298, -1202560850, 1572022689, -19854097, -538011812, 134453198, -328364711, 754211028, -623506431, 708652979, -1701361236, 754211028, -534601298, -979453453, 498820948}

    Returns: 84

  41. {850374041, -452435125, -270833029, 1173484882, -452435125, -270833029, 850374041, -83443999, -226230674, 575905448, 802580611, 1009401678, -452435125, 1464808776, -308404349, 74068174, -166965734, 300653338, 1214394821, -452435125, 51672587, 854253198, -283828773, 854253198, -452435125, -1683252938, 752923527, -1133859689, -1348417877, 501063584}

    Returns: 107

  42. {-399528715, -129194197, -188173052, -77644332, 545060329, 485090118, 116715558, -177590827, 116715558, 603913596, -1042506467, -1065675744, 1110311214, -154415927, 485090118, 454460883, 939551001, 1056266559, -1268807917, -1065675744, -1095268856, 9708325, -1055967419, 454460883, 485090118, -314749888, -1095268856, -365222270, 794281223, 360209526, 412316241, 1188086959, 520314879, 156954934, -31187073}

    Returns: 132

  43. {359892402, 45142513, -472198782, 676905441, 1530755522, -1266908324, 1530755522, 344976064, 865290943, -1125237771, -1156424844, 758774610, 234793849, -126422596, 1530755522, -743898339, 136676985, -1332110341, 196921771, 438514350, 484183625, -126422596, -229036475, 5757374, 196921771, -386575532, -1130473871, 1153686762, -178423579, 18498192, -1332110341, 107190669, 1266863233, 1266863233, 814951337, -1591937630, 168970486, -961503385, 192183377, 13759798}

    Returns: 157

  44. {-843345432, 1242715126, 1349905796, 469285381, -640371509, 403212624, 1242715126, 1406111146, 444607761, 636791138, 650550936, 682808926, 1172079458, 455062509, -1079968531, -1234818498, -193549724, 1362567385, 639417677, 64548718, 1608948, -904676255, -568246332, 1118089387, -1021256809, 493992782, -843345432, 330284767, -305385506, 1172079458, -1330539815, 818552781, -86123475, -654369806, -1683764067, -557537227, -63544446, 201426902, -583975296, 323310462, 650550936, -379933362, 665626807, 636791138, 682808926}

    Returns: 181

  45. {676157473, -879213711, 676157473, 68274365, 68274365, -1840185910, 474531788, 145317820, 676157473, -758150407, 121855856, 347492313, -1110635297, -978816486, -910542121, 1506642794, 1192368765, -946078450, -582816538, 572732409, -175352012, -1545704746, 444286033, 61384307, 1518309623, 662429473, -2033636587, 39796437, 111063632, -52284714, 68274365, 550690124, 1046450888, 550690124, 170713070, -458460955, 203968518, -1829668069, 357612016, -1678808000, 416390934, 631769139, 741129694, 1046949504, -758150407, 1518309623, -176138463, 27830055, -946078450, 385398478}

    Returns: 215

  46. {-2000000000,2000000000,0,0,0,-2000000000,2000000000,0,0,0}

    Returns: 19

  47. {50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

    Returns: 153

  48. { 4, 2, 3, 1 }

    Returns: 5

  49. { 12, 144, 151, 40 }

    Returns: 5

  50. { -20000, 20000, 0, 0, 0, -20000, 20000, 0, 0, 0 }

    Returns: 19

  51. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }

    Returns: 151

  52. { 23947, 20, -102, 30, 30, 20, 340, -122, 0, 0, 3, 0, 0, 489, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 63

  53. { 200000000, 2, 3, 4, -2000000, 0, 0, 99, 99, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 100, 200000 }

    Returns: 58

  54. { 2, 3, 3 }

    Returns: 2

  55. { 5, 4, 3 }

    Returns: 3

  56. { 1, 2, 3, 4, 5, 6 }

    Returns: 7

  57. { 4, 2, 3, 1 }

    Returns: 5

  58. { 12, 144, 151, 40 }

    Returns: 5

  59. { -20000, 20000, 0, 0, 0, -20000, 20000, 0, 0, 0 }

    Returns: 19

  60. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }

    Returns: 151

  61. { 23947, 20, -102, 30, 30, 20, 340, -122, 0, 0, 3, 0, 0, 489, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 63

  62. { 200000000, 2, 3, 4, -2000000, 0, 0, 99, 99, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 100, 200000 }

    Returns: 58

  63. { 2, 3, 3 }

    Returns: 2

  64. { 5, 4, 3 }

    Returns: 3

  65. { 1, 2, 3, 4, 5, 6 }

    Returns: 7

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: