MergeSort

MergeSort

package sort;

import java.util.Arrays;

/*MergeSort is DIVIDE AND CONQUER
 DIVIDE - divide the array recursively till it contains single element (1-->half-->quarter ...so on)
 CONQUER - merge the divided arrays in sorted order
 
 * */


/**
 * @author sachin4java@blogspot.com
 *
 */
public class MergeSort {

public static void main(String[] args) {
int arr[] = {64,25,12,22,11};
System.out.println("Given array"+Arrays.toString(arr));
       sort(arr,0,arr.length-1);
       System.out.println("Sorted array"+Arrays.toString(arr));

}

public static void sort(int[] arr, int start, int end){

if(start<end){
//find middle
int m = (start+end)/2;
//divide the array recursively
sort(arr,start,m);
sort(arr,m+1,end);

//merge the above divided arrays in sorted order

merge(arr, start,m,end);


}

}

private static void merge(int[] arr, int start, int m, int end) {
//first create left and right arrays
//sizes of arrays
int s1 = m-start+1;
int s2 = end-m;

int left[] = new int[s1];
int right[] = new int[s2];

//copy the elemnts of arrays
for (int i = 0; i < s1; ++i) {
left[i]=arr[start+i];
}
for (int i = 0; i < s2; ++i) {
right[i]=arr[m+1+i];
}

//now merge in sorted fashion
int i=0,j=0;//for start index of left and right arrays
int k=start;// this will keep the index position in main array
while(i<s1 && j<s2){

if(left[i]<=right[j]){
arr[k]=left[i];
i++;
}else {
arr[k]=right[j];
j++;

}
//increment index by 1
k++;

}
//also there are possibilities that array having some remaaining elements
//lets add it in maain array with index k
while(i<s1){
arr[k]=left[i];
i++;
k++;
}
while(j<s2){
arr[k]=right[j];
j++;;
k++;
}


}

}

OUTPUT:

Given array[64, 25, 12, 22, 11]

Sorted array[11, 12, 22, 25, 64]