Merge Sort in Java: An Efficient Sorting Algorithm

In this article, we will explore the merge sort in Java. We will provide a sample Java code, explain the logic steps, discuss the time and space complexity, it’s applications and finally conclude.

Table of Contents

Sample Java Code

Here is an implementation of merge sort in Java:


import java.util.*;

public class MergeSort {
  
  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);
    }
  }
  
  public static void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];
    
    for (int i = 0; i < n1; i++) {
      leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
      rightArr[j] = arr[mid + 1 + j];
    }
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
      if (leftArr[i] <= rightArr[j]) {
        arr[k] = leftArr[i];
        i++;
      } else {
        arr[k] = rightArr[j];
        j++;
      }
      k++;
    }
    
    while (i < n1) {
      arr[k] = leftArr[i];
      i++;
      k++;
    }
    
    while (j < n2) {
      arr[k] = rightArr[j];
      j++;
      k++;
    }
  }
  
  public static void main(String[] args) {
    int[] arr = {5, 2, 8, 12, 1, 6};
    System.out.println("Original array: " + Arrays.toString(arr));
    mergeSort(arr, 0, arr.length - 1);
    System.out.println("Sorted array: " + Arrays.toString(arr));
  }
}

Output

Original array: [5, 2, 8, 12, 1, 6]
Sorted array: [1, 2, 5, 6, 8, 12]

Logic Steps

The merge sort algorithm follows a divide-and-conquer approach.
It recursively divides the input array into two halves until each half contains only one element.
Then it merges the two sorted halves to create a sorted array.

Time Complexity

The time complexity of merge sort in Java in the worst case is O(n log n), where n is the number of elements in the array. It provides consistent performance regardless of the initial order of the elements.

Space Complexity

The space complexity of merge sort is O(n), where n is the number of elements in the array. It requires additional space to store the temporary arrays during the merge step.

Applications of Merge Sort

Merge sort, as an efficient sorting algorithm, finds its application in various real-life scenarios. Let’s look into some of the notable examples:

Sorting Large Datasets: Merge sort’s ability to handle large datasets with good performance makes it ideal for sorting large amounts of data.
External Sorting: Merge sort is ideal for external sorting, handling large datasets that cannot fit into memory. It efficiently utilizes disk I/O operations, minimizing disk accesses when sorting large files or processing data on external storage devices.
Network Packet Routing: In network routing algorithms, merge sort plays a crucial role in sorting and merging network packets.
Merge Operations in Database Systems: Merge sort is commonly used in database systems for merging multiple sorted lists efficiently. It enables efficient operations like merging two sorted tables or indexes.
Parallel Computing: Merge sort is suitable for parallel computing, as it can be divided into independent subproblems, enabling faster sorting of large datasets by utilizing multiple processors or cores.
File Merge Operations: Merge sort is often used in file merge operations, where multiple sorted files need to be merged into a single sorted file.

Conclusion: Merge Sort in Java

Merge sort is an efficient sorting algorithm that guarantees a stable and consistent performance. It divides the array into smaller parts, sorts them individually, and then merges them to obtain the final sorted array.

By using the merge sort in Java, you can effectively and reliably sort arrays of any size.

Understanding and implementing different sorting algorithms like merge sort in Java will enhance your problem-solving skills and broaden your knowledge of efficient algorithms.

Related Articles: