Sorting Algorithms - #3 merge Sort

hi👋Devs,

I hope you getting some things from this Sorting Algorithms series.
in this article, we will discuss the very efficient and fast algorithm, Merge Sort algorithms.

Merge Sort

Merge Sort algorithm is based on the divide & conquer principle which states that repeatedly breaks down the problem into sub-problem, solves each sub-problem individually, and combines the sub-problem solutions into a final solution.

Let's understand this algorithm in a much better way with an example.

step-1 find the mid point and recursively divide the array into two subarrays until the array size becomes 1.

step-2 merge the two subarrays into an array till the final array is merged, in ascending order.

Pseudocode for recursively divide the array into two sub-arrays.

step-1 initialise left & right index of an array.

step-2 return if array size is 1.
if left >= right return.

step-3 find the mid of the array.
mid = (left + right) / 2

step-4 divide the array into two sub-array.
divide( array, left, mid)
divide( array, mid+1, right)

step-5 merge the two sub-array into a array.
marge( array, left, mid, right)

Pseudocode for merge the two sub-arrays.

step-1 calculate the size of left & right sub-arrays.
leftArrSize = mid - left+1
rightArrSize = right - mid

step-2 initialise the temps arrays for left & right sub-arrays
leftArr[]
rightArr[]

step-3 copy sub-arrays into the temp arrays.

leftArr[] = array[left....mid]
rightArr[] = array[mid+1...right]

step-4 set initial indexes of subarrays & array.
leftPointer = 0
rightPointer = 0
arrPointer = left

step-5 copy the temp sub-arrays into an array, in ascending or descending order, till the end of any temp sub-arrays.

step-6 copy the remaining elements of temp sub-arrays.

see the java implementation

Java

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {

      int[] arr = new int[]{5,9,2,7,1,10,4,1,50};

      System.out.println("unsorted Array : "+Arrays.toString(arr));

      mergeSort(arr,0,arr.length-1); 

      System.out.println("sorted Array in ascending order : "+Arrays.toString(arr));
    }

   private static void mergeSort(int[] arr,int left,int right){

    // return if arr size becomes 1
    if(left >= right) return;


    // calculate the mid
    int mid = ( left + right ) / 2;

    // divide the array into two subarrays
    mergeSort(arr,left,mid);
    mergeSort(arr,mid+1,right);

    // merge subarrays
    merge(arr,left,mid,right);

   }

   private static void merge(int[] arr,int left,int mid,int right){

    // calculate the size of left & right subarrays
    int leftArrSize = mid - left+1;
    int rightArrSize = right - mid;

    // initialise temp subarrays
    int[] leftArr = new int[leftArrSize];
    int[] rightArr = new int[rightArrSize];

    // copy left & right array into temp arrays
    for (int i = 0; i < leftArrSize; ++i)
      leftArr[i] = arr[left + i];
    for (int j = 0; j < rightArrSize; ++j)
    rightArr[j] = arr[mid + 1 + j];

    // set initial indexes of subarrays
    int leftPointer = 0;
    int rightPointer = 0;
    int arrPointer = left;

    // copy temp subarrays, in ascending order
    while(leftPointer < leftArrSize && rightPointer < rightArrSize ){

      if(leftArr[leftPointer] <= rightArr[rightPointer]){
        arr[arrPointer] = leftArr[leftPointer];
        arrPointer++;
        leftPointer++;
      }else{
        arr[arrPointer] = rightArr[rightPointer];
        arrPointer++;
        rightPointer++;
      }
    }


    // copy the remaining elements of left subarray into a marge array
    while(leftPointer < leftArrSize){
      arr[arrPointer] = leftArr[leftPointer];
      arrPointer++;
      leftPointer++;
    }

    // copy the remaining elements of right subarray into a merge array
    while(rightPointer < rightArrSize){
      arr[arrPointer] = rightArr[rightPointer];
      arrPointer++;
      rightPointer++;
    }



   }
}

Thank you for reading this article. share this article with your dev friends and save it for the future.

Blog

Sorting Algorithms - #3 merge Sort

sachin26

Merge Sort

Java

Join Our Newsletter. No Spam, Only the good stuff.

Related