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