Merge Sort Algorithm in DSA Java - Build from Scratch

Merge Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. You will implement the Merge Sort algorithm step-by-step to sort an array of integers.

🎯 Goal: Build a Java program that sorts an array of integers using the Merge Sort algorithm. You will create the initial array, set up helper variables, implement the merge sort logic, and finally print the sorted array.

📋 What You'll Learn

Create an integer array called arr with the exact values: 38, 27, 43, 3, 9, 82, 10

Create a helper integer array called temp of the same length as arr

Implement the mergeSort method that takes the array, the helper array, and the start and end indices

Implement the merge method to merge two sorted halves

Call mergeSort on the entire array

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Merge sort is used in many software systems to sort large datasets efficiently, such as sorting records in databases or organizing data for search.

💼 Career

Understanding merge sort helps in technical interviews and is essential for roles involving algorithm design, data processing, and software development.

1

Create the initial array

Create an integer array called arr with these exact values: 38, 27, 43, 3, 9, 82, 10

DSA Java

# Create the integer array arr with the given values
// Your code here

Hint

Use int[] arr = {38, 27, 43, 3, 9, 82, 10}; to create the array.

2

Create the helper array

Create an integer array called temp with the same length as arr inside the main method

DSA Java

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        // Create the helper array temp with the same length as arr
        // Your code here
    }
}

Hint

Use int[] temp = new int[arr.length]; to create the helper array.

3

Implement mergeSort and merge methods

Add the mergeSort method with parameters int[] arr, int[] temp, int left, int right that recursively sorts the array. Also add the merge method with parameters int[] arr, int[] temp, int left, int mid, int right that merges two sorted halves. Call mergeSort(arr, temp, 0, arr.length - 1) inside main.

DSA Java

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        int[] temp = new int[arr.length];
        // Call mergeSort on the entire array
        // Your code here
    }

    // Add mergeSort method here
    // Your code here

    // Add merge method here
    // Your code here
}

Hint

Define mergeSort to split and sort recursively, and merge to combine sorted parts. Call mergeSort in main.

4

Print the sorted array

Add a for loop in main to print each element of arr separated by spaces on one line

DSA Java

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
        // Print the sorted array elements separated by spaces
        // Your code here
    }

    public static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid + 1, right);
            merge(arr, temp, left, mid, right);
        }
    }

    public static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                i++;
            } else {
                temp[k] = arr[j];
                j++;
            }
            k++;
        }

        while (i <= mid) {
            temp[k] = arr[i];
            i++;
            k++;
        }

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

        for (int index = left; index <= right; index++) {
            arr[index] = temp[index];
        }
    }
}

Hint

Use a for loop to print each element of arr followed by a space.

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Divide the array into halves, sort each half, then merge them

B. Compare each element with every other element and swap if needed

C. Pick the smallest element and place it at the beginning repeatedly

D. Build a heap and extract elements in sorted order

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the array into two halves recursively until single elements remain.

2. Step 2: Merge sorted halves

   It then merges these sorted halves to produce a fully sorted array.

3. Final Answer:

   Divide the array into halves, sort each half, then merge them -> Option A

4. Quick Check:

   Merge Sort = Divide and Conquer [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking it sorts in place without merging
• Believing it picks smallest elements one by one

2. Which of the following is the correct way to declare the merge function header in Java for Merge Sort?

easy

A. int merge(int arr[], int left, int right)

B. void merge(int[] arr, int left, int mid, int right)

C. void merge(int arr[], int start, int end)

D. int merge(int[] arr, int mid, int right)

Solution

1. Step 1: Identify parameters needed for merging

   The merge function needs the array and three indices: left, mid, and right to merge two halves.

2. Step 2: Check return type and parameter order

   It returns nothing (void) and parameters match the signature in void merge(int[] arr, int left, int mid, int right).

3. Final Answer:

   void merge(int[] arr, int left, int mid, int right) -> Option B

4. Quick Check:

   Correct merge signature = void merge(int[] arr, int left, int mid, int right) [OK]

Hint: Merge needs array and three indices: left, mid, right [OK]

Common Mistakes:

• Using wrong parameter order
• Returning int instead of void
• Missing mid index parameter

3. What will be the output of the following Java code snippet using Merge Sort on array {4, 1, 3, 2}?

int[] arr = {4, 1, 3, 2};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 1, 3, 4]

Solution

1. Step 1: Understand mergeSort on {4,1,3,2}

   It splits into {4,1} and {3,2}, sorts each half to {1,4} and {2,3}.

2. Step 2: Merge sorted halves

   Merging {1,4} and {2,3} results in fully sorted array {1,2,3,4}.

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

   Sorted array = [1, 2, 3, 4] [OK]

Hint: Merge Sort always returns sorted array ascending [OK]

Common Mistakes:

• Confusing merge order
• Not sorting halves before merging
• Printing original unsorted array

4. Identify the bug in this merge function snippet for Merge Sort in Java:

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];
  for (int j = 0; j < n2; j++) R[j] = arr[mid + j];
  // merging logic follows...
}

medium

A. Array L should be of size n1 + 1

B. Lengths n1 and n2 should be mid - left + 1 and right - mid

C. Copying elements from arr to R should start from mid + 1

D. No bug, code is correct

Solution

1. Step 1: Check array lengths and copying ranges

   Lengths n1 = mid - left + 1 and n2 = right - mid are correct for the left half (left to mid) and right half (mid+1 to right).

2. Step 2: Verify copying elements to R array

   Copying to R starts at arr[mid], but it should start at arr[mid + 1] to avoid overlap.

3. Final Answer:

   Copying elements from arr to R should start from mid + 1 -> Option C

4. Quick Check:

   Right half copy starts at mid+1 [OK]

Hint: Right half starts copying from mid+1, not mid [OK]

Common Mistakes:

• Starting right half copy at mid instead of mid+1
• Incorrect array length calculation
• Assuming no overlap in copying

5. Given an array with many duplicate elements, how can you modify Merge Sort to maintain the original order of equal elements (stable sort)?

hard

A. When merging, always pick from the right subarray first

B. Merge Sort cannot be stable with duplicates

C. Use a hash map to track duplicates and reorder after sorting

D. When merging, if elements are equal, pick from the left subarray first

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps equal elements in their original order.

2. Step 2: Modify merge step for stability

   When merging, if elements are equal, always choose the element from the left subarray first to preserve order.

3. Final Answer:

   When merging, if elements are equal, pick from the left subarray first -> Option D

4. Quick Check:

   Stable merge picks left element first on ties [OK]

Hint: Pick left element first when equal to keep order [OK]

Common Mistakes:

• Picking right element first breaks stability
• Thinking Merge Sort is unstable by default
• Using extra data structures unnecessarily