Implementation of merge sort in Java

          In previous post, implemented the Selection Sort in Java.  In this post, we can implement the merge sort and also discuss the time complexity.

          Merge Sort is a fast, recursive, stable sort algorithm which works by the divide and conquer principle. The algorithm has a complexity of O(n log (n)). Merge Sort is similar to Quick Sort(Will implement in the next post) the list of elements which should be sorted is divided into two lists. These lists are sorted independently and then combined. During the combination of the lists the elements are inserted (or merged) on the correct place in the list.

It involves the following steps,

• Divide the array into two (or more) sub arrays.
• Sort each sub array (Conquer).
• Merge them into one (in a smart way)

See the below diagram,

MergeSort.java,

package com.test;

public class MergeSort {
        private int[] arr;
        private int[] temp;
        private int length;
     

        public static void main(String a[]){
             int[] arr = {60,8,44,71,33,96,12,10,46};
  
             System.out.println("Array before sorting:--");
             for(int i=0;i < arr.length;i++){
                  System.out.println(arr[i]);
             } 
  
             MergeSort mers = new MergeSort();
             mers.sort(arr);
        
             System.out.println("Array after sorting:--");
             for(int i:arr){
                  System.out.println(i);
             }
        }
    

        public void sort(int arr[]) {
             this.arr = arr;
             this.length = arr.length;
             this.temp = new int[length];
             MergeSortArr(0, length - 1);
        }
    

        private void MergeSortArr(int lowIndex, int highIndex) {
             if (lowIndex < highIndex) {
                  int middle = lowIndex + (highIndex - lowIndex) / 2;
                  MergeSortArr(lowIndex, middle);
                  MergeSortArr(middle + 1, highIndex);
                  MergeSortArr1(lowIndex, middle, highIndex);
             }
        }
    

        private void MergeSortArr1(int lowIndex, int middle, int highIndex) {
             for (int i = lowIndex; i <= highIndex; i++) {
                    temp[i] = arr[i];
             }
             int i = lowIndex;
             int j = middle + 1;
             int k = lowIndex;
             while (i <= middle && j <= highIndex) {
                  if (temp[i] <= temp[j]) {
                       arr[k] = temp[i];
                       i++;
                  } else {
                      arr[k] = temp[j];
                      j++;
                 }
                 k++;
             }
             while (i <= middle) {
                 arr[k] = temp[i];
                 k++;
                 i++;
             }
 
        }
 }

Output:--

Array before sorting:--

60

8

44

71

33

96

12

10

46

Array after sorting:--

8

10

12

33

44

46

60

71

96


Related Post:-
1) Java Program to implement Selection Sort
2) Java Program for Bubble Sort in Ascending and Descending order
3) Java Program to Sort ArrayList of Custom Objects By Property using Comparator interface
4) Java Program to Reverse a Linked List using Recursion and Loops