Merge Sort

Merge Sort: This sorting algorithm works on the following principle - Divide the array in two halves. Repeatedly sort each half, then merge two halves.

Lets say we have an array A[ ] = { 9, 7, 8, 3, 2, 1} .

First we will divide it in two halves A1 [ ] = {9, 7, 8} and A2[ ] = {3, 2, 1}. Again divide these 2 halves in their two halves. For A1 it will be A1_a[ ] = {9, 7} and A1_b[ ] = {8}. Again, divide A1_a and then as they further cannot be divided, so merge them by comparing them. A1_a will be {7, 9} and then compare and merge A1_a and A1_b. Now, A1 will be { 7, 8, 9} . Do same for A2 and then A2 will be {1, 2, 3} . Now, compare A1 and A2 and then merge them. Now, A will be {1, 2, 3, 7, 8, 9}.

complexity:Array with n elements is divided recursively in 2 parts, so it will form a tree with nodes asdivided parts of array (subproblems).The height of the tree will be log₂n and at each level of tree the computation cost of all the subproblems will be n. At each level the merge operation will take O( n) time.So the overall complexity of this algorithm will be O( n(log₂ n)).

Here in merge function, we will merge the two part of arrays where one part has starting and ending positions from start to mid respectively and another part has positions from mid+1 to end.

We will start from starting positions of both the parts that are p and q.Then we will compare respective elements of both the parts and the one with the smaller value will be stored in the auxiliary array. If at some condition ,one part comes to end ,then all the elements of another part of array are added in the auxiliary array in the same order they exist.

import java.util.Scanner;

class Merge

{

void sort(int arr[],int n)

{

int left[];

int right[];

if(arr.length<2)

return;

int mid=arr.length/2;

left=new int[mid];

right=new int[arr.length-mid];

for(int i=0;i<mid;i++)

left[i]=arr[i];

for(int i=mid;i<n;i++)

right[i-mid]=arr[i];

sort(left,left.length);

sort(right,right.length);

Merge m2=new Merge();

m2.merge(arr,right,left);

}

void merge(int arr[],int right[],int left[])

{

int i=0,k=0,j=0;

while(i<left.length && j<right.length)

{

if(left[i]<=right[j])

{

arr[k]=left[i];

k++;

i++;

}

else

{

arr[k]=right[j];

k++;

j++;

}

}

while(i<left.length)

{

arr[k]=left[i];

k++;

i++;

}

while(j<right.length)

{

arr[k]=right[j];

k++;

j++;

}

}

}

class MergeTest

{

public static void main(String args[])

{

Merge m1=new Merge();

Scanner sc=new Scanner(System.in);

System.out.println("enter the total number of elements:");

int n=sc.nextInt();

int a[]=new int [n];

for(int i=0;i<n;i++)

{

System.out.printf("enter the %d elements:",i+1);

a[i]=sc.nextInt();

}

m1.sort(a,n);

System.out.println("the sorted array is:");

for(int i=0;i<n;i++)

System.out.print(a[i]+"\t");

}

}