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.

Merge Sort in Java

Now that we've examined one of the most simplest and inefficient sorting algorithms (Bubble Sort), lets have a look at O(nlogn) sorts. To start with, we shall look into Merge Sort.
Merge Sort follows divide and conquer technique. The following is a simple pictorial illustration of the same.

There will be two parts in this sort. One would be halving the input numbers O(logn) and the other would be merging them back O(n) which results in a comprehensive O(nlogn) time. Wait till you see the running version of this sort technique and the time taken to sort a million entries.

First for the code part,

package dsa.sorting;

public class MergeSortOptimized
{

    public static int SIZE = 1000000;

    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();
        MergeSortOptimized mNew = new MergeSortOptimized();
        mNew.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("Time taken to sort a million elements : "
                + (end - start) + " milliseconds");
    }

    public int[] sort(int[] input)
    {
        int[] temp = new int[input.length];
        mergeSort(input, temp, 0, input.length - 1);
        return input;
    }

    public void mergeSort(int[] fromArray, int[] toArray, int left, int right)
    {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(fromArray, toArray, left, center);
            mergeSort(fromArray, toArray, center + 1, right);
            merge(fromArray, toArray, left, center + 1, right);
        }
    }

    public void merge(int[] fromArray, int[] toArray, int leftPos,
            int rightPos, int rightEnd)
    {
        int leftEnd = rightPos - 1;
        int tempPos = leftPos;

        int numElements = rightEnd - leftPos + 1;

        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (fromArray[leftPos] < fromArray[rightPos]) {
                toArray[tempPos++] = fromArray[leftPos++];
            }
            else {
                toArray[tempPos++] = fromArray[rightPos++];
            }
        }

        while (leftPos <= leftEnd) {
            toArray[tempPos++] = fromArray[leftPos++];
        }
        while (rightPos <= rightEnd) {
            toArray[tempPos++] = fromArray[rightPos++];
        }

        for (int i = 0; i < numElements; i++, rightEnd--) {
            fromArray[rightEnd] = toArray[rightEnd];
        }

    }

}
// Time taken to sort a million elements : 247 milliseconds

As you may observe, the above technique just took 247 milliseconds to sort a million elements whereas the bubble sort tooks almost 28 seconds to sort a hundred thousand elements!!!!! This is due to the logarithmic order of the sort.

Pros:
1) Works in O(nlogn) time.
2) Worst case of merge sort is equal to best case of a quick sort! (We shall discuss more about in the coming sections).

Cons:
1) Consumes extra space.
2) Due to the recursive nature of the algorithm, may eat up stack.

Thanks for reading my post. We shall explore more sorting techniques in the coming days. Till then, bye for now from,
Bragaadeesh.

Java Sorting techniques

I thought i would start exploring the Sorting mechanisms in Data Structures and try to comprehensively implement them in Java.

We have many types of sorting techniques readily available and there are numerous amount of resources in the net with ready made coding in all the common languages. What I have done here is, did some research on each of the sorting techniques and tried to present the most commonly used sorting techniques with its pros and cons. I have not dealt or dug deep into 'alternate' techniques but have provided a sufficient overview with running code.

Today I will present two of the most familiar sorting techniques namely bubble sort and merge sort and discuss its pros and cons in the following posts.

Cheers,
Bragaadeesh