Merge Sort is a Divide and Conquer algorithm that divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sub-arrays into a single sorted sub-array.


public class MergeSort {
  public void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[] = new int[n1];
    int R[] = new int[n2];
    for (int i = 0; i < n1; ++i)
      L[i] = arr[l + i];
    for (int j = 0; j < n2; ++j)
      R[j] = arr[m + 1 + j];
    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
      if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
      } else {
        arr[k] = R[j];
        j++;
      }
      k++;
    }
    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }
    while (j < n2) {
      arr[k] = R[j];
      j++;
      k++;
    }
  }
  
  public void sort(int arr[], int l, int r) {
    if (l < r) {
      int m = (l + r) / 2;
      sort(arr, l, m);
      sort(arr, m + 1, r);
      merge(arr, l, m, r);
    }
  }
}

Algorithm Steps:

1. Divide the unsorted list into n sublists, each containing one element.

2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.

Complexity:

Time Complexity: O(n log n) in all cases. Space Complexity: O(n).

Bottom-Up Merge Sort

Bottom-Up Approach:

This approach starts with merging pairs of elements, then merges pairs of sorted pairs, and so on until the entire list is merged.


public class BottomUpMergeSort {
  public void mergeSort(int[] array) {
    int n = array.length;
    int[] temp = new int[n];
    for (int size = 1; size < n; size *= 2) {
      for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * size) {
        int mid = Math.min(leftStart + size - 1, n - 1);
        int rightEnd = Math.min(leftStart + 2 * size - 1, n - 1);
        merge(array, temp, leftStart, mid, rightEnd);
      }
    }
  }

  private void merge(int[] array, int[] temp, int leftStart, int mid, int rightEnd) {
    System.arraycopy(array, leftStart, temp, leftStart, rightEnd - leftStart + 1);
    int i = leftStart, j = mid + 1, k = leftStart;
    while (i <= mid && j <= rightEnd) {
      if (temp[i] <= temp[j]) {
        array[k++] = temp[i++];
      } else {
        array[k++] = temp[j++];
      }
    }
    while (i <= mid) {
      array[k++] = temp[i++];
    }
  }
}

Key Points:

This version of merge sort does not use recursion, instead it iteratively merges subarrays of increasing size.

Merge Sort with Linked List

Linked List Implementation:

Merge Sort can also be implemented on linked lists, which is often more efficient than array-based merges.


class Node {
  int data;
  Node next;
  Node(int d) { data = d; next = null; }
}

class LinkedList {
  Node head;

  Node sortedMerge(Node a, Node b) {
    Node result = null;
    if (a == null) return b;
    if (b == null) return a;
    if (a.data <= b.data) {
      result = a;
      result.next = sortedMerge(a.next, b);
    } else {
      result = b;
      result.next = sortedMerge(a, b.next);
    }
    return result;
  }

  Node mergeSort(Node h) {
    if (h == null || h.next == null) return h;
    Node middle = getMiddle(h);
    Node nextofmiddle = middle.next;
    middle.next = null;
    Node left = mergeSort(h);
    Node right = mergeSort(nextofmiddle);
    Node sortedlist = sortedMerge(left, right);
    return sortedlist;
  }

  Node getMiddle(Node h) {
    if (h == null) return h;
    Node slow = h, fast = h.next;
    while (fast != null) {
      fast = fast.next;
      if (fast != null) {
        slow = slow.next;
        fast = fast.next;
      }
    }
    return slow;
  }
}

Advantages:

Merge Sort is preferred for linked lists because it does not require random access to data, which is costly in linked lists.

Parallel Merge Sort

Parallel Processing:

Parallel Merge Sort uses multiple threads to divide the array into subarrays and sort them concurrently, improving performance on multi-core systems.


import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

public class ParallelMergeSort extends RecursiveAction {
  private int[] array;
  private int left;
  private int right;

  public ParallelMergeSort(int[] array, int left, int right) {
    this.array = array;
    this.left = left;
    this.right = right;
  }

  @Override
  protected void compute() {
    if (left < right) {
      int mid = (left + right) / 2;
      ParallelMergeSort leftTask = new ParallelMergeSort(array, left, mid);
      ParallelMergeSort rightTask = new ParallelMergeSort(array, mid + 1, right);
      invokeAll(leftTask, rightTask);
      merge(array, left, mid, right);
    }
  }

  private void merge(int[] array, 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];
    System.arraycopy(array, left, L, 0, n1);
    System.arraycopy(array, mid + 1, R, 0, n2);
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
      if (L[i] <= R[j]) {
        array[k++] = L[i++];
      } else {
        array[k++] = R[j++];
      }
    }
    while (i < n1) {
      array[k++] = L[i++];
    }
    while (j < n2) {
      array[k++] = R[j++];
    }
  }

  public static void parallelMergeSort(int[] array) {
    ForkJoinPool pool = new ForkJoinPool();
    pool.invoke(new ParallelMergeSort(array, 0, array.length - 1));
  }
}

Benefits of Parallelization:

By utilizing multiple threads, the sorting process can be significantly sped up, especially for large datasets.

Merge Sort with In-Place Merging

In-Place Merge Sort:

This variation aims to reduce the space complexity by performing the merge operation in-place.


public class InPlaceMergeSort {
  public void mergeSort(int[] arr, int start, int end) {
    if (start < end) {
      int mid = (start + end) / 2;
      mergeSort(arr, start, mid);
      mergeSort(arr, mid + 1, end);
      mergeInPlace(arr, start, mid, end);
    }
  }

  private void mergeInPlace(int[] arr, int start, int mid, int end) {
    int start2 = mid + 1;
    if (arr[mid] <= arr[start2]) {
      return;
    }
    while (start <= mid && start2 <= end) {
      if (arr[start] <= arr[start2]) {
        start++;
      } else {
        int value = arr[start2];
        int index = start2;
        while (index != start) {
          arr[index] = arr[index - 1];
          index--;
        }
        arr[start] = value;
        start++;
        mid++;
        start2++;
      }
    }
  }
}

Space Efficiency:

This method reduces the space complexity from O(n) to O(1) by avoiding the use of temporary arrays.