Merge sorting with example and program

Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sub-lists in a manner that results into a sorted list.
Sorting by merging is a recursive, divide-and-conquer strategy. In the base case, we have a sequence with exactly one element in it. Since such a sequence is already sorted, there is nothing to be done. To sort a sequence of n>1 elements:

1. Divide the sequence into two sequences of length [n/2] and [n/2]

2. Recursively sort each of the two sub sequences; and then

3. Merge the sorted sub sequence to obtain the final result.

Example:

  Example:

class MergeSort
{ int[] a;
int[] tmp;
MergeSort(int[] arr)
{ a = arr;
tmp = new int[a.length];
}
void msort()
{ sort(0, a.length-1); }
void sort(int left, int right)
{
if(left < right)
{
int mid =(left+right)/2;
sort(left, mid);
sort(mid+1, right);
merge(left, mid, right);
}
}
void merge(int left, int mid, int right)
{ int i = left;
int j = left;
int k = mid+1;
while( j<= mid && k <= right )
{
if(a[j] < a[k])
tmp[i++] = a[j++];
else
tmp[i++] = a[k++];
}
while( j <= mid )
tmp[i++] = a[j++];
for(i=left; i < k; i++)
a[i] = tmp[i];
}
}
//////////////////// MergeSortDemo.java ///////////////////////
class MergeSortDemo
{ public static void main(String[] args)
{ int[] arr ={75, 40, 10, 90, 50, 95, 55, 15, 65};
MergeSort ms = new MergeSort(arr);
ms.msort();
System.out.print("Sorted array:");
for( int i=0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}

 

Time complexity of merger sort