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:

Post a Comment