If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
Merge sort is divide and conquer sorting algorithm. It is efficient, comparison based sorting algorithm.
Table of Contents
Merge sort Algorithm
It works on below principle:
Dividelist intosublistof about half size in each iteration until each sublist has only one element.Mergeeachsublistrepeatedly to create sorted list. It will run until we have only 1 sorted list. This will be thesorted list.
Merge sort implementation
I have printed intermediate steps to understand algorithm better.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
package org.arpit.java2blog; public class MergeSortMain { /* * @author: Arpit Mandliya */ static int arr[]={100,20,15,30,5,75,40}; public static void main(String args[]) { // Print array before merge sort System.out.println("Array before sorting:"); printArray(arr,0,arr.length-1); System.out.println("-----------------------------"); mergeSort(0,arr.length-1); System.out.println("-----------------------------"); // Print array after sorting System.out.println("Array After sorting:"); printArray(arr,0,arr.length-1); } // Recursive algorithm for merge sort public static void mergeSort(int start,int end) { int mid=(start+end)/2; if(start<end) { // Sort left half mergeSort(start,mid); // Sort right half mergeSort(mid+1,end); // Merge left and right half merge(start,mid,end); } } private static void merge(int start, int mid, int end) { // Initializing temp array and index int[] tempArray=new int[arr.length]; int tempArrayIndex=start; System.out.print("Before Merging: "); printArray(arr,start,end); int startIndex=start; int midIndex=mid+1; // It will iterate until smaller list reaches to the end while(startIndex<=mid && midIndex<=end) { if(arr[startIndex]< arr[midIndex]) { tempArray[tempArrayIndex++]=arr[startIndex++]; } else { tempArray[tempArrayIndex++]=arr[midIndex++]; } } // Copy remaining elements while(startIndex<=mid) { tempArray[tempArrayIndex++]=arr[startIndex++]; } while(midIndex<=end) { tempArray[tempArrayIndex++]=arr[midIndex++]; } // Copy tempArray to actual array after sorting for (int i = start; i <=end; i++) { arr[i]=tempArray[i]; } System.out.print("After merging: "); printArray(tempArray,start,end); System.out.println(); } public static void printArray(int arr[],int start,int end) { for (int i = start; i <=end; i++) { System.out.print(arr[i]+" "); } System.out.println(); } } |
100 20 15 30 5 75 40
—————————–
Before Merging: 100 20
After merging: 20 100
Before Merging: 15 30
After merging: 15 30
Before Merging: 20 100 15 30
After merging: 15 20 30 100
Before Merging: 5 75
After merging: 5 75
Before Merging: 5 75 40
After merging: 5 40 75
Before Merging: 15 20 30 100 5 40 75
After merging: 5 15 20 30 40 75 100
—————————–
Array After sorting:
5 15 20 30 40 75 100
Time Complexity
Best case: O(nlogn)
Average case: O(nlogn)
Worst case: O(nlogn)
To understand more about complexity,please go through complexity of algorithm.
Please go through java interview programs for more such programs.
