How to Implement the Merge Sort Algorithm

Introduction

Sorting algorithms play a crucial role in computer science, and one of the most efficient and widely used ones is Merge Sort. This blog post explores the Merge Sort algorithm, its working mechanism, and its implementation in Java.

What is Merge Sort?

Merge Sort is an algorithm based on a divide and rule strategy. It works by breaking apart an array into smaller subarrays, recursively sorting the subarrays, and then merging them. It is O(n log n) in all cases, making it highly efficient compared to other algorithms like Bubble Sort or Insertion Sort.

How Merge Sort Works Step by Step

We can implement the Merge Sort algorithm using the following recursive steps:

1. Split the array into two subarrays and sort each until they contain a single element.
2. Merge the sorted subarrays back into a single sorted array.

Implementation of Merge Sort by Java Code

Here is an example of Merge Sort implemented in Java as a Junit test:

	@Test
	public void mergeSortTest() throws Exception {
        int[] a = {110, 47, 77, 26, 91, 54, 87};       
        mergeSort(a, 0, a.length - 1);
        for (int elem : a) {
            System.out.println(elem + " ");
        }
	}

    private void mergeSort(int[] arrayToSort, int l, int r) {
        if (l < r) {
            int middle = l + (r - l) / 2;         
            mergeSort(arrayToSort, l, middle);
            mergeSort(arrayToSort, middle + 1, r);            
            merge(arrayToSort, l, middle, r);
        }
    }
    
    private void merge(int[] arrayToMerge, int l, int middle, int r) {
        int k1 = middle - l + 1;
        int k2 = r - middle;
        
        int[] leftArray = new int[k1];
        int[] rightArray = new int[k2];
        
        for (int i = 0; i < k1; i++)
            leftArray[i] = arrayToMerge[l + i];
        for (int j = 0; j < k2; j++)
            rightArray[j] = arrayToMerge[middle + 1 + j];
        
        int i = 0, j = 0, k = l;
        while (i < k1 && j < k2) {
            if (leftArray[i] <= rightArray[j]) {
            	arrayToMerge[k] = leftArray[i];
                i++;
            } else {
            	arrayToMerge[k] = rightArray[j];
                j++;
            }
            k++;
        }
        
        while (i < k1) {
        	arrayToMerge[k] = leftArray[i];
            i++;
            k++;
        }
        
        while (j < k2) {
        	arrayToMerge[k] = rightArray[j];
            j++;
            k++;
        }
    }

Complexity Analysis

• Best: O(n log n) (Original array already sorted )
• Average: O(n log n)
• Worst: O(n log n) (Original array sorted in reverse order)
• Space Complexity: O(n)

Advantages and Disadvantages

Advantages

• Guarantees O(n log n) performance.
• Stable sorting algorithm (maintains the relative order of equal elements).
• Well-suited for sorting linked lists.

Disadvantages

• Requires additional memory for temporary arrays.
• Slower than Quick Sort for smaller datasets.

Conclusion

Merge Sort is a powerful and reliable sorting algorithm with consistent performance. Although it requires extra space, its stability and efficiency make it a great choice for many applications. If you need a predictable and stable sort, Merge Sort is an excellent option.

You can find the example code on Github.