Merge Sort is based on a divide and conquer algorithm. It is very easy to implement, and very fast sorting technique. The efficiency/performance is approximately equal to m.log (m). As the algorithm based on divide and conquer it divide an array until each divided array has only one element i.e. it divide n elements array to n arrays. Than it merges again and again in pair with sorting the array.
Suppose we have
Implementation of Merge Sort in Java Example:-
package mergesort;
import java.util.Random;
public class MergeSort
{
private int size;
private int []list;
MergeSort(int size)
{
this.size = size;
list = new int[size];
generate(list, size);
}
public int[] getList()
{
return list;
}
public void setList(int[] list)
{
this.list = list;
}
public static void main(String[] args)
{
MergeSort obj = new MergeSort(5);
System.out.print("Unsorted List is ");
for(int i : obj.getList())
System.out.print(i + ",");
System.out.println();
obj.mergesort(obj.getList());
System.out.print("Sorted List is ");
for(int i : obj.getList())
System.out.print(i + ",");
System.out.println();
}
private void generate(int []a, int size)
{
Random rand = new Random();
for (int i = 0; i < size ; i++)
{
a[i] = rand.nextInt(100) + 1000;
}
}
private void mergesort (int []list)
{
int tempArr[] = new int[size];
divideList(list,tempArr,0,size-1);
}
private void divideList(int []list, int []tempArr, int low, int high)
{
int pivot;
if(low<high)
{
pivot=(low+high)/2;
// Recursive
divideList(list,tempArr,low,pivot);
divideList(list,tempArr,pivot+1,high);
merge(list,tempArr,low,pivot,high);
}
}
// it is similar to quick sort
private void merge(int []list, int []tempArr, int low, int pivot, int high)
{
int h, i, j, k;
h = low;
i = low;
j = pivot + 1;
while((h<=pivot)&&(j<=high))
{
if(list[h]<=list[j])
{
tempArr[i]=list[h++];
}
else
{
tempArr[i]=list[j++];
}
i++;
}
if(h>pivot)
{
for(k=j; k<=high; k++)
{
tempArr[i++]=list[k];
}
}
else
{
for(k=h; k<=pivot; k++)
{
tempArr[i++]=list[k];
}
}
for(k=low; k<=high; k++)
list[k]=tempArr[k];
}
}
Output:-
Unsorted List is 1029,1040,1083,1058.
Sorted List is 1029,1040,1058,1083.
Explanation of java Merge Sort:-
divideList is calling recursively so it will grow in a stack.
First divideList statement will call 2 times because in 2nd call the if condition if(low<high) will fail stack will grow with depth 4 like below.
First Stack:
divideList(list, tempArr, 0, 0) // below two statement would be like that in stack divideList(list,tempArr,pivot+1,high) (list,tempArr,1,1) merge(list,tempArr,low,pivot,high); (list,tempArr,0,0,1); divideList(list, tempArr, 0, 1) // below two statement would be like that in stack divideList(list,tempArr,pivot+1,high) (list,tempArr,2,3) merge(list,tempArr,low,pivot,high); (list,tempArr,0,1,3);
So now from stack top.
divideList(list, tempArr, 0, 0).
// below two statement would be like that in stack.
divideList(list,tempArr,pivot+1,high).
(list,tempArr,1,1).
merge(list,tempArr,low,pivot,high);
(list,tempArr,0,0,1);
divideList(list, tempArr, 1, 1) will call as if condition (low < high) will fail it will exit.
Next statement in stack is merge(list,tempArr,0,0,1); will call and will do quick sort
i.e two element 1029 and 1040 will got to merge function as 1029 is less than 1040 modified list would be
1029 1040 1083 1058
Now Stack will pop up and now we have only one element in stack which is
divideList(list, tempArr, 0, 1) // below two statement would be like that in stack divideList(list,tempArr,pivot+1,high) (list,tempArr,2,3) merge(list,tempArr,low,pivot,high); (list,tempArr,0,1,3);
So from this stack last two statement will call.
The First statement is divideList(list,tempArr,2,3).
So it will grow a new stack as if condition (if (low< high) is true.
divideList(list, tempArr, 2, 2) // below two statement would be like that in stack divideList(list,tempArr,pivot+1,high) (list,tempArr,3,3) merge(list,tempArr,low,pivot,high); (list,tempArr,2,2,3);
So this stack as only one element so it will run divideList(list,tempArr,3,3) as if condition failed so immediately it will call next statement merge(list,tempArr,2,2,3);
i.e it will sort 2nd and third element from the list 1029 1040 1083 1058 and merge will give 1029 1040 1058 1083.
Now merge statement merge(list,tempArr,0,1,3) will call. I.e. it will sort 1 to 3rd element from 1029 1040 1058 1083.
Now merger statement will sort 1040 1058 1083 and finally it will give 1029 1040 1058 1083.
In above we can see that divideList called total 7 times.
