Memory/performance of merge sort code

Question

I wrote up merge sort code for some late night snack. I have gotten it working, but was just looking learn if I was missing anything in terms of efficiency. Could this code be significantly improved in terms of efficiency (space/time/unnecessary checks)?

package com.komal.sort;
import java.util.Arrays;
import java.util.Date;

public class MergeSort {

    static int a[]= {1,2,7,4,5,8,12,54,23,66,22,312,65,23,65,867,222,21,1000};

    public static void main(String[] args) {    

        System.out.println(new Date());
        System.out.println("input length: "+ a.length);
        int [] result =new MergeSort().mergeSort("start", a);
        System.out.println("Result: "+Arrays.toString(result));
        System.out.println("\nResult array size: "+ result.length);
        System.out.println("\n"+new Date());


    }

    public int[] mergeSort( String subTree, int [] a)
    {
        System.out.println("MergeSort.mergeSort():"+subTree+" inputs:"+ Arrays.toString(a));
        if(a.length>1)
        {
            int[] leftArray= Arrays.copyOfRange(a, 0, (a.length/2));
            int[] rightArray= Arrays.copyOfRange(a, (a.length/2), a.length);                        
            return merge(mergeSort("left", leftArray),  mergeSort("right",rightArray));
        }
        return a;
    }

    public int[] merge(int[] leftArray, int[] rightArray)
    {

        int[] input = new int[leftArray.length+ rightArray.length]; 
        int left=0;
        int i=0;
        int right=0;
        while(left+right!= leftArray.length + rightArray.length)
        {
            if(left>=leftArray.length ){                
                input[i]= rightArray[right];
                i++;
                right++;                
            }
            else if(right>=rightArray.length ){             
                input[i]= leftArray[left];
                i++;
                left++; 
            }
            else{

                if(leftArray[left]<rightArray[right])
                {
                    input[i]= leftArray[left];
                    i++;
                    left++;
                }else{

                    input[i]= rightArray[right];
                    i++;
                    right++;
                }
            }
        }       


        return input;
    }
}

Output:

Sun Jun 05 01:26:23 IST 2016
input length: 19
MergeSort.mergeSort():start inputs:[1, 2, 7, 4, 5, 8, 12, 54, 23, 66, 22, 312, 65, 23, 65, 867, 222, 21, 1000]
MergeSort.mergeSort():left inputs:[1, 2, 7, 4, 5, 8, 12, 54, 23]
MergeSort.mergeSort():left inputs:[1, 2, 7, 4]
MergeSort.mergeSort():left inputs:[1, 2]
MergeSort.mergeSort():left inputs:[1]
MergeSort.mergeSort():right inputs:[2]
MergeSort.mergeSort():right inputs:[7, 4]
MergeSort.mergeSort():left inputs:[7]
MergeSort.mergeSort():right inputs:[4]
MergeSort.mergeSort():right inputs:[5, 8, 12, 54, 23]
MergeSort.mergeSort():left inputs:[5, 8]
MergeSort.mergeSort():left inputs:[5]
MergeSort.mergeSort():right inputs:[8]
MergeSort.mergeSort():right inputs:[12, 54, 23]
MergeSort.mergeSort():left inputs:[12]
MergeSort.mergeSort():right inputs:[54, 23]
MergeSort.mergeSort():left inputs:[54]
MergeSort.mergeSort():right inputs:[23]
MergeSort.mergeSort():right inputs:[66, 22, 312, 65, 23, 65, 867, 222, 21, 1000]
MergeSort.mergeSort():left inputs:[66, 22, 312, 65, 23]
MergeSort.mergeSort():left inputs:[66, 22]
MergeSort.mergeSort():left inputs:[66]
MergeSort.mergeSort():right inputs:[22]
MergeSort.mergeSort():right inputs:[312, 65, 23]
MergeSort.mergeSort():left inputs:[312]
MergeSort.mergeSort():right inputs:[65, 23]
MergeSort.mergeSort():left inputs:[65]
MergeSort.mergeSort():right inputs:[23]
MergeSort.mergeSort():right inputs:[65, 867, 222, 21, 1000]
MergeSort.mergeSort():left inputs:[65, 867]
MergeSort.mergeSort():left inputs:[65]
MergeSort.mergeSort():right inputs:[867]
MergeSort.mergeSort():right inputs:[222, 21, 1000]
MergeSort.mergeSort():left inputs:[222]
MergeSort.mergeSort():right inputs:[21, 1000]
MergeSort.mergeSort():left inputs:[21]
MergeSort.mergeSort():right inputs:[1000]
Result: [1, 2, 4, 5, 7, 8, 12, 21, 22, 23, 23, 54, 65, 65, 66, 222, 312, 867, 1000]

Result array size: 19

Sun Jun 05 01:26:23 IST 2016

Answer 1

Unnecessary array creation

The mergeSort method creates leftArray and rightArray, but it doesn't really need to. merge could use a single input array with start, middle and end indexes. The reduced array creation will optimize the performance, though it will not change the order of complexity.

Inefficient merging

The conditions throughout the merge step are not organized efficiently.

First of all, for each target element, this condition is evaluated:

left + right != leftArray.length + rightArray.length

Instead of using leftArray.length + rightArray.length, you could use the target length that is already known without addition. But in any case, this condition is not very expressive, it just reveals that we haven't reached the end of one of the arrays, and inside the loop body we still need to check again if reached the end of one of them.

A more efficient and clearer way to organize the conditions is to use 3 loops:

    while (left < leftArray.length && right < rightArray.length) {
        if (leftArray[left] < rightArray[right]) {
            input[i++] = leftArray[left++];
        } else {
            input[i++] = rightArray[right++];
        }
    }
    while (left < leftArray.length) {
        input[i++] = leftArray[left++];
    }
    while (right < rightArray.length) {
        input[i++] = rightArray[right++];
    }

Naming

input is not a good name for an array that in fact stores the output of a method.

Answer 2

Interface

Two interface designs are acceptable. A simple function:

public class MergeSort {
    // Suppress the default constructor
    private MergeSort() {}
    public static int[] sort(int[] a) { … }
}

or an object-oriented design:

interface IntegerSort {
    int[] sort(int[] a);
}

public class MergeSort implements IntegerSort {
    public int[] sort(int[] a) { … }
}

In comparison, you have:

• a function whose name is redundant with the class
• the function taking an unusual String parameter as a debugging aid
• a publicly exposed merge() method

Instrumentation

If I had to pick one of the functions to trace, I would pick merge() instead, since it is more error-prone, and you don't need to artificially introduce the left/right distinction.

A better way to add debugging output would be to use the Java logging API. Create the following logging.properties file:

handlers = java.util.logging.ConsoleHandler
MergeSort.level = ALL
java.util.logging.ConsoleHandler.level = ALL

Then execute the solution below using java -enableassertions -Djava.util.logging.config.file=logging.properties MergeSort.

You printed timestamps, presumably as a way to measure performance. However, java.util.Date is only precise to the second, which isn't useful. Even then, you can't meaningfully measure performance while you are also spewing debugging output, since the printing itself would account for much of the time spent. (The default logging handlers happen to print timestamps on all messages.)

Merge

The input array is poorly named. It isn't the input — it's the output!

The loop is cumbersome. A for loop would be easier to read. The termination check could just be i < output.length — whether the output has been filled up. The loop copies one element to the output per iteration, so the i++ should be factored out. (The code below is a variant of your original code. The way @janos wrote it is a bit more efficient.)

You have a bit of a bug: your merge routine is not stable. A stable sort has the property that if two elements in the input are equal to each other, then they will not be swapped in the output. Mergesort can be stable if implemented well, therefore it is generally expected that it be implemented with the stability property. When sorting primitives, it makes no difference, but the issue does become relevant when sorting objects, so you might as well do it "right". To make your sort stable, simply change if(leftArray[left]<rightArray[right]) to if (leftArray[left] <= rightArray[right]).

import java.util.Arrays;
import java.util.logging.Logger;

public class MergeSort {
    private static final Logger logger = Logger.getLogger("MergeSort");

    public static void main(String[] args) {    
        int a[] = {1,2,7,4,5,8,12,54,23,66,22,312,65,23,65,867,222,21,1000};

        System.out.println("Input:  " + Arrays.toString(a));
        int [] result = new MergeSort().sort(a);
        System.out.println("Result: " + Arrays.toString(result));
        assert a.length == result.length;
    }

    public int[] sort(int[] a) {
        if (a.length > 1) {
            int[] leftArray = Arrays.copyOfRange(a, 0, (a.length/2));
            int[] rightArray = Arrays.copyOfRange(a, (a.length/2), a.length);
            return merge(sort(leftArray),  sort(rightArray));
        }
        return a;
    }

    private int[] merge(int[] leftArray, int[] rightArray) {
        logger.entering(this.getClass().getName(), "merge",
                        new Object[] { Arrays.toString(leftArray),
                                       Arrays.toString(rightArray) });

        int[] output = new int[leftArray.length + rightArray.length]; 
        for (int left = 0, right = 0, i = 0; i < output.length; i++) {
            if (right >= rightArray.length) {
                output[i] = leftArray[left++];
            } else if (left >= leftArray.length) {
                output[i] = rightArray[right++];
            } else if (leftArray[left] <= rightArray[right]) {
                output[i] = leftArray[left++];
            } else {
                output[i] = rightArray[right++];
            }
        }

        logger.exiting(this.getClass().getName(), "merge", Arrays.toString(output));
        return output;
    }
}

Answer 3

1 main

I understand that you print Date objects in order to measure how much time your implementation takes. There is, however, a better way:

long startTime = System.nanoTime();
new MergeSort().mergeSort(...);
long endTime = System.nanoTime();

System.out.printf("MergeSort.mergeSort in %.3f seconds.\n",
                  (endTime - startTime) / 1e9);

2 mergeSort

1. Printing to standard output in an algorithm is a big no-no. Consider what happens if your friend wants to include your implementation in his project: he will be overwhelmed with all the output, and printing will slow down your algorithm essentially, since printing to standard output is not computationally cheap.

2. public int[] mergeSort( String subTree, int [] a) Please do not pass debugging related arguments to an algorithm, at least in the production version. Also, the JDK convention is that sorting algorithms do not return a sorted copy of the input array, but rather modify the contents of the input array such that they end up sorted. Also, use consistent spacing; instead of

   public int[] mergeSort( String subTree, int [] a)
   

   write

   public int[] mergeSort(String subTree, int[] a)
   

   Also, the convention is that you put a single space between any binary operator, so that int left=0; becomes int left = 0; and if(a.length>1) becomes if(a.length > 1). Also, the condition of an if must be surrounded with a space as well; so that if(a.length>1){ becomes if (a.length > 1) {. Finally, the convention for writing a curly brace separated blocks are as follows:

   if (test1()) {
       ...
   } else if (test2()) {
       ...
   } else {
       ...
   }
   

Summa summarum

You can make your mergesort implementation more efficient by allocating the auxiliary array once and reusing it on all levels of recursion, and that is how you could do it:

package com.komal.sort;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    public static void main(String[] args) {
        System.out.println("[STATUS] Warming up...");

        warmup();

        System.out.println("[STATUS] Warming up done!");

        long seed = System.nanoTime();
        Random random = new Random(seed);

        int[] array1 = getRandomIntArray(10_000_000, random);
        int[] array2 = array1.clone();

        System.out.println("Seed = " + seed);

        long startTime = System.nanoTime();

        array1 = new MergeSort().mergeSort(null, array1);

        long endTime= System.nanoTime();

        System.out.printf("MergeSort.mergeSort in %.3f seconds.\n",
                          (endTime - startTime) / 1e9);

        startTime = System.nanoTime();

        coderoddeMergesort(array2);

        endTime= System.nanoTime();

        System.out.printf("coderoddeMergesort in %.3f seconds.\n",
                          (endTime - startTime) / 1e9);

        System.out.println("Algorithms agree: " + Arrays.equals(array1,
                                                                array2));
    }

    public int[] mergeSort(String subTree, int[] a) {
        //System.out.println("MergeSort.mergeSort():" + subTree + " inputs:" + Arrays.toString(a));
        if (a.length > 1) {
            int[] leftArray = Arrays.copyOfRange(a, 0, (a.length / 2));
            int[] rightArray = Arrays.copyOfRange(a, (a.length / 2), a.length);
            return merge(mergeSort("left", leftArray), mergeSort("right", rightArray));
        }
        return a;
    }

    public int[] merge(int[] leftArray, int[] rightArray) {

        int[] input = new int[leftArray.length + rightArray.length];
        int left = 0;
        int i = 0;
        int right = 0;
        while (left + right != leftArray.length + rightArray.length) {
            if (left >= leftArray.length) {
                input[i] = rightArray[right];
                i++;
                right++;
            } else if (right >= rightArray.length) {
                input[i] = leftArray[left];
                i++;
                left++;
            } else {

                if (leftArray[left] < rightArray[right]) {
                    input[i] = leftArray[left];
                    i++;
                    left++;
                } else {

                    input[i] = rightArray[right];
                    i++;
                    right++;
                }
            }
        }

        return input;
    }

    public static void coderoddeMergesort(int[] array) {
        coderoddeMergesort(array, 0, array.length);
    }

    public static void coderoddeMergesort(int[] array, 
                                          int fromIndex, 
                                          int toIndex) {
        int[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
        coderoddeMergesort(aux, array, 0, fromIndex, toIndex - fromIndex);
    }

    private static void coderoddeMergesort(int[] source,
                                           int[] target,
                                           int sourceOffset,
                                           int targetOffset,
                                           int rangeLength) {
        if (rangeLength < 2) {
            return;
        }

        int halfRangeLength = rangeLength >>> 1;

        coderoddeMergesort(target,
                           source,
                           targetOffset,
                           sourceOffset,
                           halfRangeLength);

        coderoddeMergesort(target,
                           source, 
                           targetOffset + halfRangeLength,
                           sourceOffset + halfRangeLength,
                           rangeLength  - halfRangeLength);

        int left  = sourceOffset;
        int right = sourceOffset + halfRangeLength;

        final int leftBound  = right;
        final int rightBound = sourceOffset + rangeLength;

        int targetIndex = targetOffset;

        while (left < leftBound && right < rightBound) {
            target[targetIndex++] =
                    source[right] < source[left] ?
                    source[right++] :
                    source[left++];
        }

        System.arraycopy(source, 
                         left, 
                         target, 
                         targetIndex, 
                         leftBound - left);

        System.arraycopy(source, 
                         right, 
                         target, 
                         targetIndex, 
                         rightBound - right);
    }

    private static int[] getRandomIntArray(int size, Random random) {
        return random.ints(size).toArray();
    }

    private static void warmup() {
        Random random = new Random();

        for (int i = 0; i < 100; ++i) {
            int[] array1 = getRandomIntArray(100_000, random);
            int[] array2 = array1.clone();

            new MergeSort().mergeSort(null, array1);
            coderoddeMergesort(array2);
        }
    }
}

The performance figures are as follows:

[STATUS] Warming up...
[STATUS] Warming up done!
Seed = 125467395877067
MergeSort.mergeSort in 3.815 seconds.
coderoddeMergesort in 2.251 seconds.
Algorithms agree: true

Hope that helps.