Merge sort efficiency

Question

I've written this Java code to implement merge sort:

import java.util.*;

public class MergeSort {

    int[] a;

    MergeSort() {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of items: ");
        a = new int[scan.nextInt()];

        for (int i = 0; i < a.length; ++i) {
            a[i] = scan.nextInt();
        }

    }

    int[] mergeSort2(int beg, int end) {
        if (beg == end) {
            int []result = new int[]{a[beg]};         /****new array allocation****/
            return result;
        } 

        int[] left = mergeSort2(beg, (beg + end) / 2); 
        int[] right = mergeSort2((beg + end) / 2 + 1, end); 
        int[] result = new int[end - beg + 1];        /****new array allocation****/
        System.out.println("left.length = "+left.length+", right.length = "+right.length+", result.length = "+result.length);


        int i, l, r;  
        for (i = 0, l = 0, r = 0; l < left.length && r < right.length; ++i) {
            if (left[l] >= right[r]) {
                result[i] = right[r];
                r++;
            } else if (left[l] < right[r]) {
                result[i] = left[l];
                l++;
            }
        }

        if (l == left.length) {
            for (; r < right.length; ++r, ++i) {
                result[i] = right[r];
            }
        } else if (r == right.length) {
            for (; l < left.length; ++l, ++i) {
                result[i] = left[l];
            }
        } 
        return result;
    } 


    public static void main(String[] args) {
        MergeSort ms = new MergeSort();
        int[] result = ms.mergeSort2(0, ms.a.length - 1);
        System.out.println();
        for (int i = 0; i < result.length; ++i) {
            System.out.print(result[i] + " ");
        }
    }
}

Every time I want to return left and right to merge into result, I've to allocate result again (same for cases where length == 1). How can I avoid this allocation during recursion?

Answer 1

You can use a temporary array, see for example here or here.

As this would change quite a lot, I'm not going to rewrite your code to match those examples.

But I do have some additional comments which might improve the readability and ease of use of your code:

Constructor

A constructor should only construct an object. Your constructor also gathers user input. This makes it extremely hard to test your class.

Just let MergeSort accept an array, which you created in a ConsoleInput class (or main).

Or pass the array directly to the sort method and just use an empty constructor.

Merging

Your merging code is a bit confusing, because you are using for loops when while would be a better fit:

    int l = 0;
    int r = 0;
    int arrayPosition = 0;
    while (l < left.length && r < right.length) {
        if (left[l] >= right[r]) {
            result[arrayPosition] = right[r];
            r++;
        } else {
            result[arrayPosition] = left[l];
            l++;
        }
        arrayPosition++;
    }

    // copy rest
    while (l < left.length) {
        result[arrayPosition] = left[l];
        l++;
        arrayPosition++;
    }
    while (r < right.length) {
        result[arrayPosition] = right[r];
        r++;
        arrayPosition++;
    }

With this code, you can probably also better see the similarities to the code that uses a temporary array.

And to copy the rest, you could also use arraycopy, which is probably faster:

    if (l == left.length) {
        System.arraycopy(right, r, result, arrayPosition, right.length - r);
    } else if (r == right.length) {
        System.arraycopy(left, l, result, arrayPosition, left.length - l);
    }

Other

• naming: mergeSort2 why 2? And just write beginning instead of beg, it's not that long.
• private: fields should be private (unless there is a good reason to make them public), same with methods.
• create a merge method, it makes your code easier to read.
• the caller shouldn't need to know with what parameters to call mergeSort2. I would create a public method without arguments (or which accepts the array) which then calls mergeSort2 with the correct parameters.

Answer 2

I've written the code from scratch to use only one temporary array and using static methods:

import java.util.Arrays;

public class MergeSort { 

    public static void mergeSort(int[] orig){
        int temp[] = new int[orig.length];
        mergeSorter(0, orig.length-1, orig, temp);
    }

    private static void mergeSorter(int beg, int end, int[] orig, int[] temp) {
        if (beg == end) {
            return;
        }  
        mergeSorter(beg, (beg + end) / 2, orig, temp); 
        mergeSorter((beg + end) / 2 + 1, end, orig, temp);  
        merge(beg, end, orig, temp); 
        System.arraycopy(temp, beg, orig, beg, (end-beg+1));
    } 

    private static void merge(int beg, int end, int[] orig, int[] temp){
        int s1 = beg;           //first half starting position
        int e1 = (beg+end)/2;   //first half ends here
        int s2 = (beg+end)/2+1; //second half starts here
        int e2 = end;           

        int i = beg, l = s1, r = s2;
        while(l<=e1 && r<=e2){ 
            if (orig[l] >= orig[r]) {
                temp[i] = orig[r];  
                r++;
            } else if (orig[l] < orig[r]) {
                temp[i] = orig[l];  
                l++;
            } 
            i++;
        } 

        if (l == e1+1) { 
            System.arraycopy(orig, r, temp, i, e2-r+1);  
        } else if (r == e2+1) { 
            System.arraycopy(orig, l, temp, i, e1-l+1); 
        }   
    }

    public static void main(String[] args) { 
        int[] input = new int[]{5, 6, 3, 2, 2, 9, 9, 0};    //test array
        MergeSort.mergeSort(input);
        System.out.print(Arrays.toString(input));
    }
}

Answer 3

• "Separation of concerns": don't fill the initial array from the console input in the constructor, but instead do that step in the main method. You can than reuse your class to merge arrays that come from somewhere else.

• Don't ever make class members public (ms.a).

• Be careful with variable names. a is really not informative.

• Actually, you don't need a class at all, neither do you need a member variable, neither do you need to reallocate arrays everywhere. Just define one recursive static method:

  public static void mergeSort(int[] arrayToSort, int start, int end, int[] workArray) { ... }
  

It returns nothing, but works directly on the relevant section of the array. You will also need some work array since merge sort cannot directly modify the main array without overwriting some useful data. You can just make the work array the same size as arrayToSort. You only need to create the work array once, and I don't mean once per method call. At each step use System.arraycopy to copy the relevant section from arraySort to workArray, since that method is much more efficient than copying using a for-loop.