Merge Sort Algorithm

Merge Sort is a sorting technique, it follow divide and conquer approach. Merge sort algorithm is highly efficient Considering time complexity, but it uses extra memory space which is why quick sort is many times preferred over it.

Average Case Complexity : O(n logn)
Worst Case Complexity :  O(n logn)

Basic Idea :

we divide the array into two parts, we sort the divided parts individually and then we combine the two sorted parts.

In the diagram above red blocks denotes the two divided unsorted arrays, Green denoted the sorted sub arrays and their merge results. Note- arrays having size 1 are considered sorted.

Pseudo code : 

1) Devide array in leftArray and RightArray
2) Sort leftArray
3) Sort RightArray
4) Combine leftArray and RightArray and return the result.
    01) Initialize Combined array
    02) Initialize position counters for leftArray (k) and RightArray (l)
    03) If Both leftArray and RightArray has elements left in them
               Compare the two elements and add the smaller element in Combined array at
               current location
               Update the location counters
          Else if only leftArray has elements
                Add the leftArray elements in Combined array at current location
                Update the location counters
          Else if only RightArray has elements
                Add the RightArray elements in Combined array at current location
                Update the location counters
    04) return Combined array


Java Code : 

package Sorting;

public class MergeSort {

      // method to be called to Apply sort, method returns a sorted array

      public static int[] Sort(int[] array){

            return Devide(array);

      }

     

      //Devide array, sort its parts, combine and return result

      private static int[] Devide(int[] array){

            // if array has more than one element

            if(array.length > 1){

                  int newArrayLength = array.length/2;

                  //devide array into leftArray and RightArray

                  int[] leftArray = new int[newArrayLength];

                  int[] RightArray = new int[array.length - newArrayLength];

                 

                  //fill elements in leftArray

                  for(int i = 0; i< leftArray.length; i++){

                        leftArray[i] = array[i];

                  }

                  //fill elements in RightArray

                  for(int i = 0; i< RightArray.length; i++){

                        RightArray[i] = array[i+newArrayLength];

                  }

                  //sort left part

                  leftArray = Devide(leftArray);

                  //sort right part

                  RightArray = Devide(RightArray);

                  //Combine the two sorted parts and return the result

                  return Combine(leftArray, RightArray);

            }

            //if array size = 1, consider it sorted and return it

            return array;

           

      }

      //Combine two sorted array and return sorted combined result

      private static int[] Combine(int[] leftArray, int[] rightArray){

            //Initialize the Combined array

            int[] Array = new int[leftArray.length + rightArray.length];

            //Initialize k and l counters for leftArray and RightArray

            int k = 0;

            int l = 0;

            //Run loop to fill Array

            for(int i = 0; i<Array.length; i++){

                  //if both leftArray and RightArray has elements in it

                  if(k<leftArray.length && l<rightArray.length){

                        //Compare the elements and save the smaller in Array

                        //at "i" position

                        if(leftArray[k] < rightArray[l]){

                              //if element of leftArray is smaller

                              Array[i] = leftArray[k]; //save element from leftArray

                              k++; //increment the counter of leftArray

                        }else{

                              Array[i] = rightArray[l]; //save element from RightArray

                              l++; //increment the counter of RightArray

                        }

                  }else if(k<leftArray.length){ //if only leftArray has elements

                        Array[i] = leftArray[k];//save element from leftArray

                        k++;//increment the counter of leftArray

                  }else{

                        Array[i] = rightArray[l]; //if only RightArray has elements

                        l++;//increment the counter of RightArray

                  }

            }

            return Array; //return the merged sorted array

      }

     

}