Merge Sort in Java

Q: How does merge sort work?

Merge sort is a divide-and-conquer algorithm. It splits the array into two halves, sorts each half recursively, and then merges the two sorted halves into one sorted array.

Q: Write merge sort in Java.

Java example: import java.util.Arrays; public class MergeSort { static void mergeSort(int[] arr, int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } static void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++]; } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; System.arraycopy(

Q: What is the time complexity of merge sort?

O(n log n) in the best, average and worst case. The array is halved log n times, and each level of merging processes all n elements.

Q: What is the space complexity of merge sort?

O(n) extra space for the temporary arrays used in merging, plus O(log n) for the recursion stack. This is its main drawback compared with in-place sorts.

Q: Why is mid calculated as left + (right - left) / 2?

Writing (left + right) / 2 can overflow int when both indexes are large. left + (right - left) / 2 gives the same result without overflow.

Q: Why is merge sort a good choice for linked lists?

Merging two linked lists needs no extra array, only relinking nodes, so merge sort runs in O(n log n) time with O(log n) stack space. It also does not need random access, which linked lists lack.

Q: Write a Java method that merges two sorted arrays.

Java example: static int[] merge(int[] a, int[] b) { int[] result = new int[a.length + b.length]; int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { result[k++] = (a[i] <= b[j]) ? a[i++] : b[j++]; } while (i < a.length) result[k++] = a[i++]; while (j < b.length) result[k++] = b[j++]; return result; }

Q: Write a Java method that counts inversions using merge sort.

While merging, every time an element from the right half is placed before remaining elements of the left half, each of those left elements forms an inversion: This counts inversions in O(n log n) instead of O(n 2 ).

Q: When should you choose merge sort over quick sort?

When you need stability, a guaranteed O(n log n) worst case, or you are sorting linked lists or data too large for memory (external sorting). Quick sort is usually faster for in-memory arrays of primitives.

Merge Sort in Java

Sorting is the process of arranging a list of unsorted data in a particular order, either ascending or descending. Sort algorithms play a very crucial role for organizing unsorted data and facilitating efficient searching, retrieval, and analysis.

Every sorting algorithm has a unique approach for sorting the data; these sorting algorithms are used according to the specific requirements of the problem, including data size, structure, and distribution, as well as time and space constraints.

In this tutorial, we are going to learn all about Merge Sort in Java.

Example of Merge Sort in Java

MergeSortExample.java

class MergeSortExample {

  // Merges two subarrays of arrayNumber[].
  // First subarray is arrayNumber[l..m]
  // Second subarray is arrayNumber[m+1..r]
  static void merge(int arrayNumber[], int l, int m, int r) {
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temp arrays
    int L[] = new int[n1];
    int R[] = new int[n2];

    // Copy data to temp arrays
    for (int i = 0; i < n1; ++i)
      L[i] = arrayNumber[l + i];
    for (int j = 0; j < n2; ++j)
      R[j] = arrayNumber[m + 1 + j];

    // Initial indices of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarray array
    int k = l;
    while (i < n1 && j < n2) {
      if (L[i] <= R[j]) {
        arrayNumber[k] = L[i];
        i++;
      } else {
        arrayNumber[k] = R[j];
        j++;
      }
      k++;
    }

    // Copy remaining elements of L[] if any
    while (i < n1) {
      arrayNumber[k] = L[i];
      i++;
      k++;
    }

    // Copy remaining elements of R[] if any
    while (j < n2) {
      arrayNumber[k] = R[j];
      j++;
      k++;
    }
  }

  // Function to sorts an array[l..r] using merge sort technique
  static void sort(int array[], int l, int r) {
    if (l < r) {

      // Find the middle point
      int m = l + (r - l) / 2;

      // Sort first and second halves
      sort(array, l, m);
      sort(array, m + 1, r);

      // Merge the sorted halves
      merge(array, l, m, r);
    }
  }

  // Function to print an array
  static void printArray(int arrayNumber[]) {
    int n = arrayNumber.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arrayNumber[i] + " ");
    System.out.println();
  }

  public static void main(String args[]) {
    // Creates an array
    int arrayNumber[] = { 40, 70, 90, 20, 80, 100, 60, 10, 30, 50 };

    System.out.println("Origin unsorted array is");
    printArray(arrayNumber);

    sort(arrayNumber, 0, arrayNumber.length - 1);

    System.out.println("\nSorted array is");
    printArray(arrayNumber);
  }
}

Output

Origin unsorted array is

40 70 90 20 80 100 60 10 30 50

Sorted array is

10 20 30 40 50 60 70 80 90 100

Frequently Asked Questions (FAQ)

Q1. How does merge sort work?

Merge sort is a divide-and-conquer algorithm. It splits the array into two halves, sorts each half recursively, and then merges the two sorted halves into one sorted array.

Q2. Write merge sort in Java.

MergeSort.java

import java.util.Arrays;

public class MergeSort {

    static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));   // [3, 9, 10, 27, 38, 43, 82]
    }
}

Q3. What is the time complexity of merge sort?

O(n log n) in the best, average and worst case. The array is halved log n times, and each level of merging processes all n elements.

Q4. What is the space complexity of merge sort?

O(n) extra space for the temporary arrays used in merging, plus O(log n) for the recursion stack. This is its main drawback compared with in-place sorts.

Q5. Why is mid calculated as left + (right - left) / 2?

Writing (left + right) / 2 can overflow int when both indexes are large. left + (right - left) / 2 gives the same result without overflow.

Q6. Is merge sort stable?

Yes, as long as the merge takes from the left half when values are equal (arr[i] <= arr[j]). Java's Collections.sort and Arrays.sort for objects use TimSort, a stable merge-sort hybrid.

Q7. Why is merge sort a good choice for linked lists?

Merging two linked lists needs no extra array, only relinking nodes, so merge sort runs in O(n log n) time with O(log n) stack space. It also does not need random access, which linked lists lack.

Q8. Write a Java method that merges two sorted arrays.

MergeTwoArrays.java

static int[] merge(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length) {
        result[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
    }
    while (i < a.length) result[k++] = a[i++];
    while (j < b.length) result[k++] = b[j++];
    return result;
}

Q9. Write a Java method that counts inversions using merge sort.

While merging, every time an element from the right half is placed before remaining elements of the left half, each of those left elements forms an inversion:

CountInversions.java

static long countInversions(int[] arr, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    long count = countInversions(arr, left, mid) + countInversions(arr, mid + 1, right);
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            count += mid - i + 1;       // arr[i..mid] are all greater than arr[j]
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
    return count;
}

This counts inversions in O(n log n) instead of O(n²).

Q10. When should you choose merge sort over quick sort?

When you need stability, a guaranteed O(n log n) worst case, or you are sorting linked lists or data too large for memory (external sorting). Quick sort is usually faster for in-memory arrays of primitives.

Was this tutorial helpful?

Help Us Improve

Example of Merge Sort in Java

Frequently Asked Questions (FAQ)