Merge Sort is a technique of sorting data with below steps:-
1) Divide the data recursively until it can not divide more.
2) Compare the data and sort it.
3) Merge the data again .
/* * Merge Sort is based on the concept below points:- * 1) Divide array until it can not be divide. * 2) Merge it again in sorted pattern * * */ public class MergeSort { public static int[] mergeSort(int arr[]) { //check for size if it is one then already sorted int size=arr.length; if(size==1) { return arr; } //find middle (divide an array into two half) int mid=size/2; //first half int[] fhalf=new int[mid]; //second half int[] shalf=new int[size-mid]; // Copy first half of the array for (int i = 0; i < mid; i++) { fhalf[i] = arr[i]; } // Copy second half of the array for (int i = mid; i < size; i++) { shalf[i - mid] = arr[i]; } //recursive call fhalf and shalf return merge(mergeSort(fhalf), mergeSort(shalf)); } public static int[] merge(int[] firstHalfSorted,int[] secondHalfSorted) { // First, create a new array to store the answer. int SortedArray[] = new int[firstHalfSorted.length + secondHalfSorted.length]; int m = 0; int n = 0; int count = 0; System.out.println("first array"); printArray(firstHalfSorted); System.out.println("second array"); printArray(secondHalfSorted); //compare the elements in both arary while (m<firstHalfSorted.length && n<secondHalfSorted.length) { if (firstHalfSorted[m]>secondHalfSorted[n]) { SortedArray[count]=secondHalfSorted[n]; count++; n++; } else if (firstHalfSorted[m]<secondHalfSorted[n]) { SortedArray[count]=firstHalfSorted[m]; count++; m++; } } //append the remaining elements at the end if (m!=firstHalfSorted.length) { while(m<firstHalfSorted.length){ SortedArray[count]=firstHalfSorted[m]; count++; m++; } } //append the remaining elements at the end if (n!=secondHalfSorted.length) { while(n<secondHalfSorted.length){ SortedArray[count]=secondHalfSorted[n]; count++; n++; } } System.out.println("sorted array"); printArray(SortedArray); // At last return the sorted array return SortedArray; } public static void printArray(int[] arr) { //System.out.println("printing array"); for(int i=0;i<arr.length;i++) { System.out.print(arr[i]+" "); } System.out.println(" "); } public static void main(String[] args) { int arr[]={14,33,27,10,25,19,40,45}; printArray(arr); //calling merge function arr=mergeSort(arr); printArray(arr); } }
Implementation Steps:-
14 33 27 10 25 19 40 45 first array 14 second array 33 sorted array 14 33 first array 27 second array 10 sorted array 10 27 first array 14 33 second array 10 27 sorted array 10 14 27 33 first array 25 second array 19 sorted array 19 25 first array 40 second array 45 sorted array 40 45 first array 19 25 second array 40 45 sorted array 19 25 40 45 first array 10 14 27 33 second array 19 25 40 45 sorted array 10 14 19 25 27 33 40 45 10 14 19 25 27 33 40 45
Comments
Post a Comment