Merge Sort in Java with O(n log n) Time Complexity

In this video lesson we will study how the Merge Sort algorithm works, we will analyze its time and space complexities and then we will implement it:

Problem - Merge Sort:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Your algorithm should run in O(n log n) time and use O(n) extra space.

Understanding the Problem

The core challenge of the problem is to sort an array of integers efficiently. Merge Sort is a classic sorting algorithm that uses the divide-and-conquer approach. It is significant because it guarantees a time complexity of O(n log n), making it suitable for large datasets. Common applications include sorting data in databases, file systems, and more.

Potential pitfalls include misunderstanding the recursive nature of the algorithm and mishandling the merging process, which can lead to incorrect sorting.

Approach

To solve this problem, we need to break down the array into smaller subarrays, sort those subarrays, and then merge them back together. Here’s a step-by-step approach:

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves into a single sorted array.

A naive solution might involve repeatedly finding the minimum element and building the sorted array, but this would result in O(n^2) time complexity, which is not efficient for large datasets.

Merge Sort improves on this by ensuring that each merge operation is linear in complexity, and the number of merge operations is logarithmic in the size of the array.

Algorithm

Here’s a detailed breakdown of the Merge Sort algorithm:

1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves to produce the final sorted array.

Code Implementation

Below is the Java implementation of the Merge Sort algorithm:

public class MergeSort {
    // Main function that sorts the array using merge sort
    public static void mergeSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int[] temp = new int[nums.length];
        mergeSortHelper(nums, temp, 0, nums.length - 1);
    }

    // Helper function to perform merge sort
    private static void mergeSortHelper(int[] nums, int[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSortHelper(nums, temp, left, mid);
            mergeSortHelper(nums, temp, mid + 1, right);
            merge(nums, temp, left, mid, right);
        }
    }

    // Function to merge two sorted halves
    private static void merge(int[] nums, int[] temp, int left, int mid, int right) {
        System.arraycopy(nums, left, temp, left, right - left + 1);

        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                nums[k++] = temp[i++];
            } else {
                nums[k++] = temp[j++];
            }
        }

        while (i <= mid) {
            nums[k++] = temp[i++];
        }
    }

    // Main method to test the merge sort
    public static void main(String[] args) {
        int[] nums = {3, 1, 3, 2, 5, 4};
        mergeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

Complexity Analysis

The time complexity of Merge Sort is O(n log n) because the array is divided in half log n times, and the merging process takes linear time. The space complexity is O(n) due to the temporary array used for merging.

Edge Cases

Potential edge cases include:

• An empty array: The algorithm should handle this gracefully.
• An array with one element: This is already sorted.
• An array with duplicate elements: The algorithm should correctly sort these.

For example, given the input [], the output should be []. Given the input [1], the output should be [1].

Testing

To test the solution comprehensively, consider a variety of test cases:

• Simple cases: [3, 1, 3, 2, 5, 4]
• Edge cases: [], [1]
• Large arrays: Arrays with thousands of elements to test performance.

JUnit or other testing frameworks can be used to automate these tests.

Thinking and Problem-Solving Tips

When approaching such problems, it’s essential to understand the underlying algorithm and its properties. Practice by solving similar problems and studying different sorting algorithms. Visualizing the process can also help in understanding the divide-and-conquer approach.

Conclusion

Merge Sort is a powerful sorting algorithm with guaranteed O(n log n) time complexity. Understanding and implementing it can significantly improve your problem-solving skills. Practice and explore further to master this and other algorithms.

Additional Resources

For further reading and practice problems, consider the following resources:

• GeeksforGeeks: Merge Sort
• LeetCode: Sort an Array
• Coursera: Algorithms Part I