Sorting Algorithms - #3 merge Sort
Tags: beginners, programming, webdev, tutorial
Published: 2022-01-09 12:18:58

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.

![merge sort algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6mz185c6eumearh2u68m.png)

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

![merge sort algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6f4b5z2s3r13k5faqo5j.png)


![merge sort algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o3vt3zu9odr0v4jtl37e.png)


![merge sort algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hj2a45lqdphjchu3n70h.png)

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

![merge sort algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6acv9w00u1whptx6fzjo.png)


![merge sort algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yjzrrt3vshqhw3jr4ywz.png)



![merge sort algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ntcypjl4pyemyncfsw5i.png)

>> 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

```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.