Introduction of Merge Sort

Definition

Merge sort is a sorting algorithm that follows the divide-and-conquer approach. The algorithm starts by dividing the input array into two halves, and recursively divides each of these halves until each sub-array contains only one element. Then, the sub-arrays are merged back together, in a sorted manner, until the entire original array is sorted.

Input:
nums[] = [8,6,0,1,3]

Output:
nums[] = [0,1,3,6,8]

Working of Merge Sort Algorithm (Visual)

Algorithm of Merge Sort Algorithm

1. Divide the input array into two halves.
2. Recursively sort the left half of the array.
3. Recursively sort the right half of the array.
4. Merge the two sorted halves together to create a sorted output array.

The merge step involves comparing elements from both the left and right sub-arrays and adding them to a new output array in sorted order

You can try this at:

• https://leetcode.com/problems/sort-an-array/

Code

Java

class Solution {
    public static void merge(int[] arr,int l,int mid,int h){
        int start_arr1 = l,end_arr1 = mid;
        int start_arr2 = mid+1,end_arr2 = h;
        int[] temp_arr = new int[h-l+1];
        int index = 0;
        while(start_arr1 <= end_arr1 && start_arr2 <= end_arr2){
            if(arr[start_arr1] < arr[start_arr2]){
                temp_arr[index++] = arr[start_arr1++];
            }else{
                temp_arr[index++] = arr[start_arr2++];
            }
        }
        while(start_arr1 <= end_arr1){
            temp_arr[index++] = arr[start_arr1++];
        } 
        while(start_arr2 <= end_arr2){
            temp_arr[index++] = arr[start_arr2++];
        } 
        // update the arr
        index = 0;
        for(int i=l;i<=h;i++){
            arr[i] = temp_arr[index++];
        }
        return;
    }
    public static void mergeSort(int[] arr,int l,int h){
        if(l < h){
            int mid = (l+h)/2;
            // divide into 2 halves
            mergeSort(arr, l, mid);
            mergeSort(arr, mid+1, h);
            // start merging the segments
            merge(arr, l, mid, h);
        }
    }
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return nums;       
    }
}

Cpp

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int l, int mid, int h) {
    int start_arr1 = l, end_arr1 = mid;
    int start_arr2 = mid + 1, end_arr2 = h;
    std::vector<int> temp_arr(h - l + 1);
    int index = 0;

    while (start_arr1 <= end_arr1 && start_arr2 <= end_arr2) {
        if (arr[start_arr1] < arr[start_arr2]) {
            temp_arr[index++] = arr[start_arr1++];
        } else {
            temp_arr[index++] = arr[start_arr2++];
        }
    }

    while (start_arr1 <= end_arr1) {
        temp_arr[index++] = arr[start_arr1++];
    }

    while (start_arr2 <= end_arr2) {
        temp_arr[index++] = arr[start_arr2++];
    }

    // Update the arr
    index = 0;
    for (int i = l; i <= h; i++) {
        arr[i] = temp_arr[index++];
    }
}

void mergeSort(std::vector<int>& arr, int l, int h) {
    if (l < h) {
        int mid = (l + h) / 2;

        // Divide into 2 halves
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, h);

        // Start merging the segments
        merge(arr, l, mid, h);
    }
}

std::vector<int> sortArray(std::vector<int>& nums) {
    mergeSort(nums, 0, nums.size() - 1);
    return nums;
}

Python

class Solution:
    def merge(self, arr, l, mid, h):
        start_arr1 = l
        end_arr1 = mid
        start_arr2 = mid + 1
        end_arr2 = h
        temp_arr = [0] * (h - l + 1)
        index = 0

        while start_arr1 <= end_arr1 and start_arr2 <= end_arr2:
            if arr[start_arr1] < arr[start_arr2]:
                temp_arr[index] = arr[start_arr1]
                start_arr1 += 1
            else:
                temp_arr[index] = arr[start_arr2]
                start_arr2 += 1
            index += 1

        while start_arr1 <= end_arr1:
            temp_arr[index] = arr[start_arr1]
            start_arr1 += 1
            index += 1

        while start_arr2 <= end_arr2:
            temp_arr[index] = arr[start_arr2]
            start_arr2 += 1
            index += 1

        index = 0
        for i in range(l, h + 1):
            arr[i] = temp_arr[index]
            index += 1

    def mergeSort(self, arr, l, h):
        if l < h:
            mid = (l + h) // 2
            self.mergeSort(arr, l, mid)
            self.mergeSort(arr, mid + 1, h)
            self.merge(arr, l, mid, h)

    def sortArray(self, nums):
        self.mergeSort(nums, 0, len(nums) - 1)
        return nums

Complexity

Time Complexity:

O(Nlog(N))

Space Complexity:

O(N)