Java Program to Implement Merge Sort Algorithm

Introduction

Merge sort is a popular sorting algorithm, known for its efficiency and effectiveness even with large data sets. It is a classic example of the divide-and-conquer strategy, where the problem is divided into smaller parts, solved individually, and then combined to produce the final solution. This algorithm particularly shines due to its stable and predictable O(n log n) performance and is widely used in various applications.

In this article, you will learn how to implement the merge sort algorithm in Java. You'll explore detailed examples that break down the steps of the algorithm, helping you understand how to sort arrays efficiently. By the end of this article, you master setting up the merge sort function and applying it to different data arrays.

Understanding Merge Sort Algorithm

Basic Concepts of Merge Sort

1. Recognize that merge sort divides the array into halves until each sub-array contains a single element.
2. Learn that each pair of single-element arrays merges into sorted arrays of two elements.
3. Realize these sorted arrays merge further, maintaining order, until the whole array is assembled correctly.

Algorithm Steps

1. Split the array into halves recursively until you are left with sub-arrays that cannot be divided further.
2. Merge these smaller sub-arrays into larger, sorted arrays through a merging process.
3. Continue merging until you reassemble the original array in a sorted order.

Implementing Merge Sort in Java

Preparing the Merge Function

Merge sort involves a merging mechanism that combines two sorted arrays into a single sorted array. This section implements the merge function required for the main merge sort logic.

1. Define a method merge with parameters for the array, the starting point, the midpoint, and the ending point of the arrays to be merged.

   java Copy

   public static 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];
   
       for (int i = 0; i < n1; ++i) {
           L[i] = array[left + i];
       }
       for (int j = 0; j < n2; ++j) {
           R[j] = array[mid + 1 + j];
       }
   
       int i = 0, j = 0;
       int k = left;
       while (i < n1 && j < n2) {
           if (L[i] <= R[j]) {
               array[k] = L[i];
               i++;
           } else {
               array[k] = R[j];
               j++;
           }
           k++;
       }
   
       while (i < n1) {
           array[k] = L[i];
           i++;
           k++;
       }
   
       while (j < n2) {
           array[k] = R[j];
           j++;
           k++;
       }
   }
   

   This function first copies the relevant segments of the main array to temporary arrays, then merges those arrays back into the main array, sorted order.

Writing the Merge Sort Function

The merge sort function recursively splits the array and calls the merge function to combine the arrays.

1. Implement the mergeSort function that divides the array and uses the merge function to sort and combine the parts.

   java Copy

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

   This method continually splits the array until it becomes trivially small (single elements), then begins to merge those arrays back together in sorted order.

Example: Sorting an Array

Now, execute the merge sort algorithm on an example array.

1. Apply the mergeSort method to sort an array of integers.

   java Copy

   public static void main(String[] args) {
       int[] arr = {12, 11, 13, 5, 6, 7};
   
       mergeSort(arr, 0, arr.length - 1);
   
       System.out.println("Sorted array:");
       for (int i : arr) {
           System.out.print(i + " ");
       }
   }
   

After compiling and running this Java code, you should see the numbers from the array printed in sorted order, demonstrating the merge sort algorithm has functioned as expected.

Conclusion

The merge sort algorithm is a fundamental concept that every programmer should be familiar with for handling sorting tasks efficiently. Implementing this algorithm in Java reinforces understanding of recursive techniques and array manipulation, enhancing problem-solving skills in computer science. Utilize this approach in your future projects where stability and performance are essential, ensuring your ability to handle data sorting challenges effectively.