import java.util.Scanner;

public class LabProgram $\{$

$//$ Static variable to count comparisons

static int comparisons $=0$;

$//$ Read size and create an array of size ints.

$//$ Read size ints, storing them in the array.

$//$ Return the array.

public static int$[]$ readNums$()\{$

Scanner scnr $=$ new Scanner$($System$.$in$)$;

int size $=$ scnr$.$nextInt$()$; $//$ Read array size

int$[]$ nums $=$ new int$[$size$]$; $//$ Create array for numbers

for $($int j $=0$; j $<$ size; j$++)\{$

$//$ Read the numbers

nums$[$j$]=$ scnr$.$nextInt$()$;

$\}$

return nums; $//$ Return the array

$\}$

$//$ Output the numbers in nums, separated by spaces.

$//$ No space or newline will be output before the first number or after the last.

public static void printNums$($int$[]$ nums$)\{$

for $($int i $=0$; i $<$ nums.length; i$++)\{$

System.out.print$($nums$[$i$])$;

if $($i $<$ nums.length $-1)\{$

$//$ Corrected index boundary

System.out.print$("")$;

$\}$

$\}$

$\}$

public static void merge$($int$[]$ numbers, int i$,$ int j$,$ int k$)\{$

int mergedSize $=$ k $-$ i $+1$;

int$[]$ mergedNumbers $=$ new int$[$mergedSize$]$;

int mergePos $=0$;

int leftPos $=$ i;

int rightPos $=$ j $+1$;

while $($leftPos $<=$ j && rightPos $<=$ k$)\{$

comparisons$++$; $//$ Increment comparisons

if $($numbers$[$leftPos$]<$ numbers$[$rightPos$])\{$

mergedNumbers$[$mergePos$++]=$ numbers$[$leftPos$++]$;

$\}$ else $\{$

mergedNumbers$[$mergePos$++]=$ numbers$[$rightPos$++]$;

$\}$

$\}$

while $($leftPos $<=$ j$)\{$

mergedNumbers$[$mergePos$++]=$ numbers$[$leftPos$++]$;

$\}$

while $($rightPos $<=$ k$)\{$

mergedNumbers$[$mergePos$++]=$ numbers$[$rightPos$++]$;

$\}$

for $($mergePos $=0$; mergePos $<$ mergedSize; mergePos$++)\{$

numbers$[$i $+$ mergePos$]=$ mergedNumbers$[$mergePos$]$;

$\}$

$\}$

public static void mergeSort$($int$[]$ numbers, int i$,$ int k$)\{$

if $($i $<$ k$)\{$

int j $=($i $+$ k$)/2$;

$//$ Trace output added to code in book

System.out.printf$("\%$d $\%$d $|\%$d $\%$d

$",$ i$,$ j$,$ j $+1,$ k$)$;

mergeSort$($numbers$,$ i$,$ j$)$;

mergeSort$($numbers$,$ j $+1,$ k$)$;

merge$($numbers$,$ i$,$ j$,$ k$)$;

$\}$

$\}$

public static void main$($String$[]$ args$)\{$

int$[]$ numbers $=$ readNums$()$;

System.out.print$("$unsorted: $")$;

printNums$($numbers$)$;

System.out.println$()$;

mergeSort$($numbers$,0,$ numbers.length $-1)$;

System.out.println$("$sorted: $")$;

printNums$($numbers$)$;

System.out.println$()$;

$//$ Output number of comparisons

System.out.println$("$comparisons: $"+$ comparisons$)$;

$\}$

$\}$