Solution Merge Sort

Problem Statement

Write Recursive Approach for Merge Sort.

The problem is to implement the Merge Sort algorithm using recursion. Merge Sort is an efficient sorting algorithm that follows the divide-and-conquer approach. It divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to obtain the final sorted array.

Examples

#	Input Array	Output	Explanation
1	[5, 2, 8, 3, 1, 6]	[1, 2, 3, 5, 6, 8]	The input array is divided into two halves: [5, 2, 8] and [3, 1, 6]. Each half is recursively sorted. Then, the sorted halves are merged to obtain the final sorted array.
2	[9, 4, 7, 2, 1]	[1, 2, 4, 7, 9]	The input array is divided into two halves: [9, 4] and [7, 2, 1]. Each half is recursively sorted. Then, the sorted halves are merged to obtain the final sorted array.
3	[3, 1, 2, 5, 4]	[1, 2, 3, 4, 5]	The input array is divided into two halves: [3, 1, 2] and [5, 4]. Each half is recursively sorted. Then, the sorted halves are merged to obtain the final sorted array.

Solution

The algorithm follows these steps:

Base Case: If the input array has only one element or is empty, it is already considered sorted. Return the array.
Divide: Divide the input array into two equal halves.
Recursive Call: Recursively call the merge sort function on each half to sort them.
Merge: Merge the two sorted halves by comparing the elements and placing them in the correct order.
Return: Return the merged and sorted array.

The base case ensures that when the array is divided into single elements, they are considered sorted. The recursive case divides the array into smaller halves until the base case is reached. By recursively sorting and merging the halves, the entire array is sorted.

Code

Here is the code for this algorithm:

java

import java.util.Arrays;

public class Solution {

  public static int[] mergeSort(int[] arr) {
    mergeSortRecursive(arr, 0, arr.length - 1);
    return arr;
  }

  public static void mergeSortRecursive(int[] arr, int start, int end) {
    if (start < end) {
      int mid = (start + end) / 2;
      mergeSortRecursive(arr, start, mid); // Recursive call for the left half
      mergeSortRecursive(arr, mid + 1, end); // Recursive call for the right half
      merge(arr, start, mid, end); // Merge the sorted halves
    }
  }

  public static void merge(int[] arr, int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;

    int[] left = new int[n1];
    int[] right = new int[n2];

    for (int i = 0; i < n1; ++i) left[i] = arr[start + i];
    for (int j = 0; j < n2; ++j) right[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = start;

    while (i < n1 && j < n2) {
      if (left[i] <= right[j]) {
        arr[k] = left[i];
        i++;
      } else {
        arr[k] = right[j];
        j++;
      }
      k++;
    }

    while (i < n1) {
      arr[k] = left[i];
      i++;
      k++;
    }

    while (j < n2) {
      arr[k] = right[j];
      j++;
      k++;
    }
  }

  public static void main(String[] args) {
    int[] arr = { 5, 2, 8, 3, 1, 6 };

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

    mergeSort(arr);

    System.out.println("Sorted Array:");
    System.out.println(Arrays.toString(arr));
  }
}

Time and Space Complexity

The time complexity of the Merge Sort algorithm is in the average and worst case, where n is the number of elements in the input array. This is because the algorithm divides the array into halves recursively and merges them back together. The space complexity is since it requires additional space for the temporary arrays during the merging process.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Merge Sort? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Merge Sort** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Merge Sort** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Merge Sort**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Merge Sort**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution BST Inorder Traversal Solution Quick Sort →