Understand Merge Sort Problem

Problem Name: Merge Sort
Problem Description:

Merge Sort - A Divide and Conquer Algorithm

Merge Sort is an efficient, stable, and comparison-based sorting algorithm that follows the divide and conquer paradigm. It is particularly useful for large datasets as it has a worst-case time complexity of O(n log n).

How Merge Sort Works

Merge Sort follows three main steps:

  1. Divide:
    Recursively split the array into two halves until each sub-array contains a single element.
  2. Conquer:
    Since arrays of one element are inherently sorted, we now have a collection of sorted sub-arrays.
  3. Merge:
    Combine the sorted sub-arrays to form a single sorted array. The merging process involves comparing the smallest elements of each sub-array and arranging them in order.

Example Walkthrough

Consider the array: [8, 3, 5, 4, 2, 7, 6, 1]

Step 1: Divide

[8, 3, 5, 4] | [2, 7, 6, 1]

Splitting further: [8, 3] | [5, 4] and [2, 7] | [6, 1]

Step 2: Conquer

Each sub-array with one element is considered sorted: [8] [3] [5] [4] [2] [7] [6] [1]

Step 3: Merge

Merge each pair of sub-arrays in sorted order:

  • Merge [8] and [3] → [3, 8]
  • Merge [5] and [4] → [4, 5]
  • Merge [2] and [7] → [2, 7]
  • Merge [6] and [1] → [1, 6]

Now merge these intermediate arrays:

  • Merge [3, 8] and [4, 5] → [3, 4, 5, 8]
  • Merge [2, 7] and [1, 6] → [1, 2, 6, 7]

Finally, merge [3, 4, 5, 8] and [1, 2, 6, 7] → [1, 2, 3, 4, 5, 6, 7, 8]

Summary

  • Merge Sort divides the array into halves, recursively sorts them, and then merges the sorted halves.
  • It is highly efficient with a time complexity of O(n log n).
Category:
  • Searching & Sorting
  • Arrays
Programming Language:
  • Java
Reference Link:

https://drawtocode.vercel.app/problems/merge-sort

Online IDE

Scroll down for output
Java
Output:
Loading component...
Loading component...
Tracking code (View only. In case you want to track the code, click this button):
Main Function:
INPUT: [8, 3, 5, 4, 2, 7, 6, 1]
OUTPUT: [1, 2, 3, 4, 5, 6, 7, 8]
public static void main(String args[]){
 int arr[] = { 12, 11, 13, 5, 6, 7 };
 System.out.println("Given array is");
printArray(arr);
mergeSort(arr, 0, arr.length - 1);
System.out.println("\nSorted array is");
printArray(arr);
}//function end
Helper Function:
public static void mergeSort(int[] arr, int left, int right){
if(left < right){
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left , mid , right);
}//If End
}//function end
Utility Functions and Global variables:
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}//Loop End
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}//Loop End
int i = 0, j = 0, k = left;
 while (i < n1 && j < n2) {
 if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}//If End
else {
arr[k] = R[j];
j++;
}//Else End
 k++;
}//Loop End
 while (i < n1) {
arr[k] = L[i];
i++;
 k++;
}//Loop End
 while (j < n2) {
arr[k] = R[j];
 j++;
k++;
}//Loop End
return;
}//function end
    static void printArray(int[] arr){
        for (int val : arr) {
            System.out.print(val + " ");
}//Loop End
System.out.println();
} // Function End
Privacy Policy | About