Merge Sort in Java - Naukri Code 360

Introduction

Sorting is an important and critical operation in computer science that involves arranging elements in a specific order. Among the various sorting algorithms, merge sort is quite famous for its efficiency and widespread use. It is based on the divide-and-conquer paradigm, which involves recursively breaking down the input array into smaller subarrays until they become simple enough to be sorted directly. The sorted subarrays are then merged back together to form the final sorted array. Merge sort is known for its guaranteed time complexity of O(n log n), which makes it suitable for sorting large datasets.

In this article, we will discuss the workings of merge sort, illustrate its steps, implement it in Java, analyze its complexity, and discuss its applications, advantages, and disadvantages.

How does Merge Sort work?

Merge sort is a comparison-based sorting algorithm that follows the divide-and-conquer approach. It works by dividing the unsorted array into smaller subarrays, sorting them recursively, and then merging them back together to form the final sorted array. The basic steps of merge sort are as follows:

1. Divide: If the array has more than one element, divide it into two halves: a left subarray and a right subarray.

2. Conquer: Recursively apply merge sort to both the left and right subarrays until the base case of an array with one or zero elements is reached.

3. Combine: Merge the sorted left and right subarrays back together by comparing the elements from both subarrays and placing them in the correct order in the original array.

The merging process is an important step in merge sort. It involves comparing the elements from the left and right subarrays and placing them in the correct order in a temporary array. The temporary array is then copied back to the original array.

Note: Merge sort achieves a sorted final array by recursively dividing the array and merging the sorted subarrays. The divide-and-conquer strategy allows merge sort to efficiently handle large datasets by breaking them down into smaller and more manageable subproblems.

Illustration of Merge Sort

To better understand how merge sort works, let's take an example.

Consider the below mentioned unsorted array:

[7, 2, 5, 1, 8, 3, 6, 4]

Step 1: Divide

Divide the array into two halves:

Left subarray: [7, 2, 5, 1]

Right subarray: [8, 3, 6, 4]

Step 2: Conquer

Recursively apply merge sort to the left subarray:

Divide: [7, 2] and [5, 1]

Conquer: [2, 7] and [1, 5]

Combine: [1, 2, 5, 7

Recursively apply merge sort to the right subarray:

Divide: [8, 3] and [6, 4]

Conquer: [3, 8] and [4, 6]

Combine: [3, 4, 6, 8]

Step 3: Combine

Merge the sorted left and right subarrays:

Compare 1 (left) and 3 (right), place 1 in the merged array.

Compare 2 (left) and 3 (right), place 2 in the merged array.

Compare 3 (right) and 5 (left), place 3 in the merged array.

Compare 4 (right) and 5 (left), place 4 in the merged array.

Compare 5 (left) and 6 (right), place 5 in the merged array.

Compare 6 (right) and 7 (left), place 6 in the merged array.

Place the remaining elements 7 and 8 in the merged array.

The final sorted array: [1, 2, 3, 4, 5, 6, 7, 8]

Implementation of Merge Sort

Now that we understand how merge sort works, let's see how to implement it in Java:

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 = {7, 2, 5, 1, 8, 3, 6, 4};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

You can also try this code with Online Java Compiler

Run Code

In this code:

1. The `mergeSort` method is the entry point for the merge sort algorithm. It takes an array `arr`, the left index `left`, & the right index `right` as parameters.

2. If `left` is less than `right`, the array has more than one element & needs to be divided.

3. The middle index `mid` is calculated as `(left + right) / 2`.

4. The `mergeSort` method is recursively called on the left subarray (`left` to `mid`) & the right subarray (`mid + 1` to `right`).

5. After the recursive calls, the `merge` method is called to merge the sorted subarrays.

6. The `merge` method merges the sorted left & right subarrays into a single sorted array.

7. It creates temporary arrays `leftArr` and `rightArr` to store the elements of the left and right subarrays, respectively.

8. It compares the elements from `leftArr` and `rightArr` and places them in the correct order in the original array `arr`.

9. Finally, any remaining elements in `leftArr` or `rightArr` are copied back to `arr`.

Note: The `main` method shows how to use the `mergeSort` method by creating an unsorted array, calling `mergeSort`, and printing the sorted array.

Output

[1, 2, 3, 4, 5, 6, 7, 8]

Recurrence Relation of Merge Sort

To analyze the time complexity of merge sort, we can use a recurrence relation. A recurrence relation is an equation that describes an algorithm's running time in terms of its input size.

For merge sort, the recurrence relation can be:

T(n) = 2T(n/2) + O(n)

Where:

- T(n) represents the running time of merge sort for an input size of n.

- 2T(n/2) represents the two recursive calls on sublists of size n/2.

- O(n) represents the time taken to merge the two sorted sublists.

Let's understand the recurrence relation:

1. Divide: The original list is divided into two sublists of equal size, each containing n/2 elements. This step takes constant time, O(1).

2. Conquer: Merge sort is recursively called on the two sublists. Each recursive call takes T(n/2) time.

3. Combine: Merging the two sorted sublists takes linear time, O(n), as it requires comparing and merging n elements.

Note: The recurrence relation provides a mathematical way to express the running time of merge sort and helps in analyzing its efficiency. It captures the division of the problem into smaller subproblems and the merging of the sorted sublists.

Complexity Analysis of Merge Sort

Time Complexity

As discussed in the recurrence relation, the time complexity of merge sort is O(n log n). This means that the running time of merge sort grows logarithmically with the input size n.

The recurrence relation T(n) = 2T(n/2) + O(n) can be solved using the Master Theorem or recursion tree method. The solution gives us the time complexity of O(n log n).

- The divide step takes constant time, O(1).

- The conquer step involves two recursive calls on sublists of size n/2, each taking T(n/2) time.

- The combined step, which merges the sorted sublists, takes linear time, O(n).

The total work done at each level of recursion is O(n), as merging takes linear time. The number of levels in the recursion tree is log n because the list is divided into half at each level.

Therefore, the overall time complexity of merge sort is O(n log n), which makes it one of the most efficient sorting algorithms.

Space Complexity

Merge sort has a space complexity of O(n) because it requires additional space to store the temporary arrays during the merging process.

- In the merge step, two temporary arrays are created to store the elements of the left and right sublists.

- The size of each temporary array is proportional to the size of the sublists being merged.

- In the worst case, the space required is O(n) when the recursive calls reach the base case (sublists of size 1).

Although merge sort requires additional space, it is still considered space-efficient compared to other sorting algorithms that have a space complexity of O(n^2) or higher.

Note: The time and space complexity analysis shows that merge sort is an efficient sorting algorithm, especially for large datasets. Its guaranteed time complexity of O(n log n) makes it suitable for various scenarios, and its space complexity of O(n) is acceptable in most cases.

Applications of Merge Sort

Merge sort is a versatile sorting algorithm that finds applications in various domains. Some common applications of merge sort are:

1. Sorting large datasets: Merge sort is particularly useful when dealing with large datasets because of its efficient time complexity of O(n log n). It can handle large amounts of data efficiently, making it a preferred choice for sorting huge arrays or lists.

2. External sorting: Merge sort is often used for external sorting, where the data is too large to fit into the main memory. It can efficiently sort data stored on external storage devices like hard drives by merging smaller sorted chunks.

3. Inversion count: Merge sort can be modified to count the number of inversions in an array. An inversion occurs when a larger element appears before a smaller element in the array. Counting inversions has applications in ranking and similarity measurement.

4. Divide and conquer algorithms: Merge sort serves as a classic example of the divide and conquer paradigm. It demonstrates how a problem can be divided into smaller subproblems, solved recursively, and then combined to obtain the final solution. Understanding merge sort helps in learning and implementing other divide and conquer algorithms.

5. Stable sorting: Merge sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements. This property is important in certain applications where the original order of equal elements needs to be maintained.

6. Parallel processing: Merge sort is well-suited for parallel processing because the divide step can be performed independently on different sublists. This allows for efficient utilization of multiple processors or cores, leading to faster sorting of large datasets.

7. Combining sorted arrays: Merge sort's merging step can efficiently combine two or more sorted arrays into a single sorted array. This is useful in scenarios where data is already sorted in separate arrays and we need to merge them into a single sorted array.

Advantages & Disadvantages of Merge Sort

Advantages

1. Efficient for large datasets: Merge sort has a guaranteed time complexity of O(n log n), making it highly efficient for sorting large datasets. It scales well with the input size and performs efficiently even for huge arrays or lists.

2. Stable sorting: Merge sort is a stable sorting algorithm, which means it preserves the relative order of equal elements. If two elements have the same value, their order in the sorted output will be the same as their order in the input array. This is important in certain applications where the original order needs to be maintained.

3. Predictable performance: Merge sort has a consistent running time regardless of the initial order of the elements. Whether the input array is already sorted, reversely sorted, or randomly ordered, merge sort will take the same amount of time to sort the array. This predictable performance is advantageous in scenarios where the input characteristics are unknown.

4. Suitable for external sorting: Merge sort is well-suited for external sorting, where the data is too large to fit into the main memory. It can efficiently sort data stored on external storage devices by merging smaller sorted chunks.

5. Parallelizable: Merge sort can be parallelized, allowing for efficient utilization of multiple processors or cores. The divide step can be performed independently on different sublists, enabling parallel processing and faster sorting of large datasets.

Disadvantages

1. Extra space requirement: Merge sort requires additional space proportional to the size of the input array. It uses temporary arrays to store the merged sublists during the merging process. The space complexity of merge sort is O(n), which can be a concern when working with limited memory resources.

2. Recursive nature: Merge sort is implemented using recursion, which can lead to overhead due to function calls and stack memory usage. For extremely large datasets or in systems with limited stack space, the recursive nature of merge sort may be a drawback.

3. Not in-place: Merge sort is not an in-place sorting algorithm, meaning it requires extra space to store the temporary arrays during merging. In contrast, some other sorting algorithms, like insertion sort or heap sort, can sort the array in place without requiring additional space.

Frequently Asked Questions

Is merge sort an in-place sorting algorithm?

No, merge sort is not an in-place sorting algorithm. It requires extra space to store temporary arrays during the merging process.

Can merge sort be parallelized?

Yes, merge sort can be parallelized. The divide step can be performed independently on different sublists, allowing for parallel processing.

Is merge sort a stable sorting algorithm?

Yes, merge sort is a stable sorting algorithm. It preserves the relative order of equal elements in the sorted output.

Conclusion

In this article, we have discussed the merge sort algorithm, a powerful and efficient sorting technique. We discussed its working principle, illustrated its steps, implemented it in Java, analyzed its time and space complexity, and explored its various applications. Merge sort's divide-and-conquer approach, stability, and efficiency make it a preferred choice for sorting large datasets. Despite its space overhead, merge sort remains one of the most reliable and widely used sorting algorithms in computer science.

You can also check out our other blogs on Code360.