# Is this attempt at a merge sort correct?

I am trying to write a merge sort algorithm. I can't tell if this is actually a canonical merge sort. If I knew how to calculate the runtime I would give that a go. Does anyone have any pointers?

public static void main(String[] argsv) {

int[] A = {2, 4, 5, 7, 1, 2, 3, 6};
int[] L, R;

L = new int[A.length/2];
R = new int[A.length/2];

int i = 0, j = 0, k;

PrintArray(A);
// Make left and right arrays
for (k = 0; k < A.length; k++) {
if (k < A.length/2) {
L[i] = A[k];
i++;
}
else {
R[j] = A[k];
j++;
}
}

PrintArray(L);
PrintArray(R);

i = 0;
j = 0;
// Merge the left and right arrays
for (k = 0; k < A.length; k++) {
System.out.println(i + " " + j + " " + k);
if (i < L.length && j < R.length) {
if (L[i] < R[j]) {
PrintArray(A);
A[k] = L[i];
i++;
}
else {
PrintArray(A);
A[k] = R[j];
j++;
}
}
}

PrintArray(L);
PrintArray(R);
PrintArray(A);
}

public static void PrintArray(int[] arrayToPrint) {
for (int i = 0; i < arrayToPrint.length; i++) {
System.out.print(arrayToPrint[i] + " ");
}
System.out.print("\n");
}


When a prospective employer asks you a question like this one, they most likely want to see something original. They want you to show them that you can create code and not just copy and paste bits and pieces of code.

If what you wrote works and runs correctly, then you have accomplished the answer.

Sometimes employers are trying to find out if you know the theory behind a merge sort. It looks to me like you have done that as well.

The only thing that I can think of that you could do to make your code better is to improve the naming of your variables.

int[] A = {2, 4, 5, 7, 1, 2, 3, 6};
int[] L, R;

L = new int[A.length/2];
R = new int[A.length/2];


Change them to

int[] array = {2, 4, 5, 7, 1, 2, 3, 6};
int[] leftSide;
int[] rightSide;

leftSide = new int[array.length/2];
rightSide = new int[array.length/2];


This would make it much easier to read.

• Thank you very much, I appreciate you taking the time to answer what I feel was an odd question. I suppose there must be a bunch of mergesort implementations, i.e. ones written in functional languages, ones that deal with an odd number of elements, ones that use sentinels, etc. Thanks again Malachi :) Oct 16 '12 at 21:03

If you already have a separate function for printing the arrays, then you should have others to do the sorting. A function should be responsible for doing one thing, which is essential in maintaining separation of concerns. This will also make the program easier to maintain as each segment will be separated.

You should have the array initialized in main(), pass it to the function, sort the array, return it, and pass it to the displaying function.

I would say this is a solid, workmanlike implementation of a merge sort.

I can see some areas for improvement though. As far as style goes, the most obvious improvement would be to use variable names that are longer and more descriptive. Names like A, L and R are of only fairly minimal help. Given that you have both L and R, it's pretty easy to guess that you intended them to stand for left and right respectively. I'd much rather see them spelled out though.

It may also be worth considering some algorithmic improvements. As it stands right now, you do recursive calls approximately $\log_2{N}$ deep, and make a new copy of all the data in the input array each time. That gives a space requirement of approximately $\log_2{N}$.

One easy way to reduce this would be to just keep track of the dividing line between the "left" and "right" arrays easy each call instead of creating entirely new arrays. This makes it pretty easy to reduce your space requirement to approximately 2N.

If you want to go even further, you could implement one of the in-place merging algorithms I cited in another answer.