3
\$\begingroup\$

I just learned Merge sort, and I really like this Merge sort implementation since it is very logical and very easy to follow. If I was asked in an interview to implement merge sort, will this implementation suffice?

I know creating those new arrays every time the mergeSort() method is called is bad practice. I fully understand merge sort, I can explain it in very good detail as I implement it, but will this implementation lose me some "points" because of the the way I am creating all these new arrays?

Are there any other things that may lose me some points?

public static void mergeSort(int[] a) {
    if(a.length < 2) return;

    int mid = a.length / 2;

    int[] left = new int[mid];
    int[] right = new int[a.length - mid];

    //Filling left and right arrays.
    for(int i = 0; i < left.length; i++)
        left[i] = a[i];
    for(int i = 0; i < right.length; i++)
        right[i] = a[i + mid];

    mergeSort(left);
    mergeSort(right);
    merge(left, right, a);
}

public static void merge(int[] left, int[] right, int[] a) {
    int i = 0; //For left array
    int j = 0; //For right array
    int k = 0; //For a array

    while(i < left.length && j < right.length) {
        if(left[i] <= right[j])
            a[k++] = left[i++];
        else
            a[k++] = right[j++];
    }

    //Filling remaining integers, for the array that has left over numbers.
    while(i < left.length)
        a[k++] = left[i++];
    while(j < right.length)
        a[k++] = right[j++];

}

This is tested and working.

\$\endgroup\$
  • \$\begingroup\$ its a static method and it wont create a new array in the memory it will use the same static one. \$\endgroup\$ – HAK Aug 29 '18 at 8:01
  • \$\begingroup\$ Sorry for the late reply. If you ignore it is static, treat it like public void mergeSort(int[] a). FIY, it was only static because I was writing in the main class. In practise it will be in its own class. What is your comment now? \$\endgroup\$ – Rino Leonardino Aug 31 '18 at 18:57
2
\$\begingroup\$

Here are some thoughts on things you might improve:

Always use curly braces, even when they're optional. This is a common source of errors when existing code is modified.

int i == 0; //For left array should be int leftArrayIndex = 0. Don’t use a comment to label a variable .. use the variable’s name to do that. Same thing for j and k.

mid should be midpoint, perhaps? originalArray instead of a? Variable names should be clear and descriptive. Avoid abbreviations where possible.

Almost all Java style guides put a space between if, for, or while and their opening paren. This easily differentiates them from method calls.

Variables that don’t change should be declared final.

Learn and use the libraries. In particular, System.arraycopy() is preferable to looping to manually copy array entries.

merge should be private, not public.

\$\endgroup\$
  • \$\begingroup\$ Sorry for the late reply. So what you are saying the only improvements I have are relatively minor? That is good news! So provided I make the changes, in an interview, this implementation would be totally acceptable? Is it textbook? lol \$\endgroup\$ – Rino Leonardino Aug 31 '18 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.