- Merge sort one of the recursive sorting algorithm.
- First divide the list of unsorted elements in two two parts. left half and right half.
- Divide the left part elements in to sub lists until it become single element.
- Divide right half of array or list of elements in to sub lists until it becomes one element in list.
- After dividing all elements in two parts in to single entity.
- Merge the elements into two by comparing lesser element will be first. apply same at right half
- Merge all the elements in the left part until it become single sorted list
- Now we have two sorted parts.
- Means two parts sorted in ascending order and smaller element will be in first position.
- Compare fist elements of two parts , lesser one should be takes first place in new sorted list
- New sorted list or array having only one element now.
- Compare two lists elements and place in sorting order and merge it.
- Finally we have all elements sorted.
- Compared to remaining algorithms like selection sort, insertion sort and bubble sort merge sort works faster.
- Lets see what will be the time complexity of merge sort algorithm.
Time complexity of merge sort algorithm:
1.Best case time complexity: O(n log (n))
2.Average case time complexity: O(n log (n))
3.Worst case time complexity: O(n log (n))
4.Worst case space complexity: O(n)
Merge sort in java with explanation diagram
Program#1: Java program to implement merge sort algorithm data structure
- package com.instanceofjava.mergesortalgorithm;
- public class MergeSortAlgorithm {
- private int[] resarray;
- private int[] tempMergArray;
- private int length;
- public static void main(String a[]){
- int[] inputArr ={6,42,2,32,15,8,23,4};
- System.out.println("Before sorting");
- for(int i:inputArr){
- System.out.print(i);
- System.out.print(" ");
- }
- MergeSortAlgorithm mergesortalg = new MergeSortAlgorithm();
- mergesortalg.sort(inputArr);
- System.out.println();
- System.out.println("After sorting");
- for(int i:inputArr){
- System.out.print(i);
- System.out.print(" ");
- }
- }
- public void sort(int inputArray[]) {
- this.resarray = inputArray;
- this.length = inputArray.length;
- this.tempMergArray = new int[length];
- doMergeSort(0, length - 1);
- }
- private void doMergeSort(int lowerIndex, int higherIndex) {
- if (lowerIndex < higherIndex) {
- int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
- //to sort left half of the array
- doMergeSort(lowerIndex, middle);
- // to sort right half of the array
- doMergeSort(middle + 1, higherIndex);
- //merge two halfs
- mergehalfs(lowerIndex, middle, higherIndex);
- }
- }
- private void mergehalfs(int lowerIndex, int middle, int higherIndex) {
- for (int i = lowerIndex; i <= higherIndex; i++) {
- tempMergArray[i] = resarray[i];
- }
- int i = lowerIndex;
- int j = middle + 1;
- int k = lowerIndex;
- while (i <= middle && j <= higherIndex) {
- if (tempMergArray[i] <= tempMergArray[j]) {
- resarray[k] = tempMergArray[i];
- i++;
- } else {
- resarray[k] = tempMergArray[j];
- j++;
- }
- k++;
- }
- while (i <= middle) {
- resarray[k] = tempMergArray[i];
- k++;
- i++;
- }
- }
- }
Output:
- Before sorting
- 6 42 2 32 15 8 23 4
- After sorting
- 2 4 6 8 15 23 32 42
No comments