19 January 2010

An inefficient implementation of Merge Sort in Java

It is not always enough just to understand how an algorithm works and do some theoretical calculations on the running time. We need to go to that extra step to actually implement for ourselves and check the performance. That is the only way to understand it piece by piece and that is the way that it remains in you forever.
This scenario happened to me with merge sort algorithm. I learnt how the algorithm actually worked and even implemented it in java. But found out that the performance of it was worse than a simple bubble sort!! I followed all the steps that was given in the 'theoretical' portion of the algorithm. But still my output was worse.
First take a brief look at the code
package dsa.sorting;

import java.util.Arrays;


public class MergeSort{

public static int SIZE = 100000;

public static void main(String args[]){
int[] a = new int[SIZE];
for(int i=0;i<SIZE;i++){
a[i] = (int)(Math.random()*SIZE);
}
long start = System.currentTimeMillis();
MergeSort mSort = new MergeSort();
mSort.sort(a);
long end = System.currentTimeMillis();
System.out.println("Time taken to sort a 100,000 elements : "+(end-start)+" milliseconds");
}

public int[] sort(int[] input) {
if(input.length<=1){
return input;
}
int[] left, right, result;

int mid = input.length/2;

left = Arrays.copyOfRange(input, 0, mid);
right = Arrays.copyOfRange(input,mid,input.length);

left = sort(left);
right = sort(right);

result = merge(left,right);

return result;
}

public int[] merge(int[] left, int[] right){
int[] result = new int[left.length+right.length];
int indexOfResult = 0;
while(left.length>0 && right.length>0){
if(left[0]<right[0]){
result[indexOfResult++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}else{
result[indexOfResult++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
if(left.length>0){
for(int i=0;i<left.length;i++){
result[indexOfResult++] = left[i];
}
}else{
for(int i=0;i<right.length;i++){
result[indexOfResult++] = right[i];
}
}
return result;
}
}
//Time taken to sort a 100,000 elements : 13401 milliseconds


After seeing the output, i kind of went nuts. I was clueless at the start on why my program was performing this bad! Later I realized that I was using up resources like anything through the Array.copyOfRange() method! It is a raw array copy which is simply not acceptable both in space and in time aspect.
Space - because of the in-numerous arrays that are getting created and Time - because of the heavy copy operations.

Later i realized i can use indexes to manipulate on the algorithms and just use only one extra array to do all my operations!! That is when i arrived at this.
A lesson well learnt!

Cheers,
Bragaadeesh.

No comments: