Understanding Merge Sort: A Deep Dive

Let’s dive into the very popular sorting algorithm and analyze it’s time complexity.

Today, I’d like to discuss one of the fundamental sorting algorithms in computer science: the Merge Sort.

What is Merge Sort?

Merge Sort is a divide-and-conquer algorithm that breaks down an array (or list) into smaller chunks, sorts each chunk, and then merges the sorted chunks back together. The beauty of this method lies in the merge step, which ensures that the individual pieces combine seamlessly to form a completely sorted array.

How does it work?

1. Divide: Split the array into two halves.
2. Conquer: Recursively sort both halves.
3. Merge: Combine (merge) the sorted halves to produce a single sorted array.

Java Implementation

To better understand, let’s see the Java code for Merge Sort:

public class MergeSort {

    public static void main(String[] args) {
        int[] nums = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(nums, 0, nums.length - 1);

        for (int i : nums) {
            System.out.print(i + " ");
        }
    }

    /**
     * This method is responsible for the divide and conquer part of the algorithm.
     * It divides the array into two halves, recursively sorts them, 
     * and then merges the two sorted halves.
     *
     * @param nums - The array to be sorted.
     * @param start - The starting index.
     * @param end - The ending index.
     */
    public static void mergeSort(int[] nums, int start, int end) {
        // Base condition to break out of recursive loops.
        if (start < end) {
            // Calculate the mid-point of the array.
            int mid = (start + end) / 2;

            // Recursively sort the first half.
            mergeSort(nums, start, mid);
            
            // Recursively sort the second half.
            mergeSort(nums, mid + 1, end);

            // Merge the sorted halves.
            merge(nums, start, end, mid);
        }
    }

    /**
     * This method is responsible for merging two sorted halves of the array.
     * 
     * @param nums - The array with halves to be merged.
     * @param start - The starting index of the left half.
     * @param end - The ending index of the right half.
     * @param mid - The ending index of the left half (or starting index of the right half minus one).
     */
    private static void merge(int[] nums, int start, int end, int mid) {
        // Auxiliary array to hold merged numbers temporarily.
        int[] aux = new int[end - start + 1];
        
        int i = start;  // Pointer for the left half.
        int j = mid + 1;  // Pointer for the right half.
        int k = 0;  // Index for the auxiliary array.

        // Compare and merge elements from the two halves into the auxiliary array.
        while (i <= mid && j <= end) {
            if (nums[i] <= nums[j]) {
                aux[k++] = nums[i++];
            } else {
                aux[k++] = nums[j++];
            }
        }

        // If there are remaining elements in the left half, add them to the auxiliary array.
        while (i <= mid) {
            aux[k++] = nums[i++];
        }

        // If there are remaining elements in the right half, add them to the auxiliary array.
        while (j <= end) {
            aux[k++] = nums[j++];
        }

        // Copy the sorted elements from the auxiliary array back to the original array.
        for (int value : aux) {
            nums[start++] = value;
        }
    }
}

Merge Sort Process Illustration

Merge Sort Time Complexity Analysis:

Merge Sort is a “divide and conquer” algorithm. To understand its time complexity, let’s break it down step by step:

Divide:

• At each level of the recursive algorithm, the array is divided into two halves.
• If you start with an array of size n, then you divide it into two halves, then four quarters, then eight eighths, and so on.
• This dividing continues until you’re left with individual elements. In terms of divisions, this would happen log⁡(n) times (because each time we’re dividing by 2). The log⁡log here is the base-2 logarithm.

Conquer (or Merge):

• At each level of the recursive algorithm, all the elements in the array are looked at once for the merging process. This merging step takes linear time, proportional to the number of elements, which is n.

Given the above:

• At the first level, we have 1 group of n elements.
• At the next level, we have 2 groups of n/2 elements.
• Then, 4 groups of n/4 elements.
• And so on…

If you multiply the number of groups by the number of elements in a group at each level, it’s always n.

Because there are log⁡(n) levels and each level takes n operations to merge, the total time complexity is:

Time Complexity=n × log(⁡n)=O(n log(⁡n))

Analogy to help you understand better

Imagine you’re organizing a deck of cards. Instead of sorting them directly, you divide the deck in half, then each half in half again, and so on, until you have single cards. This is the divide step, and you’ll do this division about log⁡(n) times.

Now, to put these cards back in order, you start merging cards two at a time, then four at a time, then eight, and so on. As you merge, you’re organizing. This is the conquer or merge step. Every time you merge, you look at all the cards once.

Since you divided and merged log⁡(n) times and looked at all n cards during each merge, your total steps are about n × log⁡ n.

So, in short, Merge Sort’s time complexity is O(n log⁡(n)), which means it scales really well as the number of elements increases.

Space Complexity of Merge Sort:

For the merge operation in the Merge Sort, we usually use an auxiliary array (or arrays) to temporarily store data before merging it back into the original array.

1. Auxiliary Space: In the traditional Merge Sort, every recursive call to the merge function requires its own auxiliary array. However, in practice, we don’t create a new array for every call. Instead, a single auxiliary array for the entire sorting process is often used, and portions of this array are used for different recursive calls.
2. Depth of the Recursion Tree: The recursive nature of Merge Sort means that we also consume space on the call stack. However, because the Merge Sort divides the array in half at each level, the maximum depth of the recursive call stack is log⁡(n).

Combining these observations:

1. The auxiliary space is O(n) because of the need for a temporary array of size n.
2. The call stack space is O(log(n)) because of the recursive calls. However, this space is typically overshadowed by the auxiliary space in most practical scenarios.

Hence, the dominant factor here is the auxiliary space.

The space complexity of Merge Sort is O(n).

In essence, while Merge Sort is efficient in terms of time complexity O(nlog⁡(n)), it’s not the most space-efficient algorithm due to its linear space complexity.

Wrapping up

Merge Sort is a reliable, comparison-based sorting algorithm with consistent performance characteristics. Its elegance is in its simplicity and its divide-and-conquer approach.

If you found this content useful, please follow me!