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.

Bubble Sort in Java

Bubble sort is the most simplest form of sorts available. In real lives, the bubbles formed under water tend to come up to the surface. Larger the bubble, faster it will come up. Same way in this sorting technique, we would try to push the larger value up in case of descending or vice versa.

Pros:
1. Simple to implement.
2. Very easy to understand.

Cons:
1. Runs in O(n²) complexity.
2. Severe performance issues if the sample size increases.

The java code for this sorting technique is as follows,

package dsa.sorting;

public class BubbleSort {

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

 public int[] sort(int[] input) {
  int temp;
  for (int i = 0; i < input.length; i++) {
   for (int j = i; j < input.length; j++) {
    if (input[i] > input[j]) {
     temp = input[i];
     input[i] = input[j];
     input[j] = temp;
    }
   }
  }
  return input;
 }
}
// Time taken to sort a 100000 elements : 28554 milliseconds

You may see from the above example that it takes insanely higher time for sorting only a hundred thousand elements. 29 seconds is a very poor outcome. We will look into O(nlogn) sort types on why and how it reduces this running time.

Cheers,
Bragaadeesh.