Merge sort with a comparison counter

Problem

Implement top-down merge sort on an int array and count its work.

Input: an integer n (n ≥ 0), followed by n integers.

Algorithm (follow it exactly, so the counts match):

mergeSort(lo, hi) returns immediately if lo >= hi; otherwise mid = (lo + hi) / 2, sort lo..mid, sort mid+1..hi, then merge.
The merge compares the front elements with a[i] <= a[j] (taking from the left half on ties). Every evaluation of this test counts as one comparison. Copying the leftover elements of a half costs no comparisons.
Every call of merge counts as one merge.

Output: three lines. For the input 6 / 5 2 4 6 1 3:

Sorted: [1, 2, 3, 4, 5, 6]
Comparisons: 11
Merges: 5

Use Arrays.toString for the first line; an empty array prints Sorted: [].

Your solution

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.

← D8.2 Longest common subsequence with reconstruction D9.2 Tracing quick sort with the Lomuto partition →