Java Coding Test Course, Merge Sort

It is important to understand various sorting algorithms to solve algorithm problems. In this article, we will explore the concept of Merge Sort and the process of solving problems through a Java code implementation.

Problem Description

Given an integer array as follows, use the Merge Sort algorithm to sort the array in ascending order.

Input: [38, 27, 43, 3, 9, 82, 10]
Output: [3, 9, 10, 27, 38, 43, 82]

What is Merge Sort?

Merge Sort is a type of Divide and Conquer algorithm. This algorithm generally works in the following stages:

1. Divide the given array in half.
2. Recursively sort each sub-array.
3. Merge the two sorted sub-arrays into a single sorted array.

The time complexity of Merge Sort is O(n log n), and it is classified as a stable sorting algorithm.

Implementation Process of Merge Sort

1. Dividing the Array

Continue to divide the array in half into smaller arrays. This stage continues until the size of the array is 1.

2. Merging and Sorting

Once each of the divided arrays is sorted, a process to merge them back together is required. At this time, the two arrays are compared and merged in a sorted order.

3. Implementing Java Code

Now, let’s implement the Merge Sort algorithm in Java.

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before Sorting: " + java.util.Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("After Sorting: " + java.util.Arrays.toString(arr));
    }

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

            // Sort the left half
            mergeSort(arr, left, mid);
            // Sort the right half
            mergeSort(arr, mid + 1, right);
            // Merge
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        // Calculate the size of left and right parts
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temporary arrays
        System.arraycopy(arr, left, L, 0, n1);
        System.arraycopy(arr, mid + 1, R, 0, n2);

        // Merging process
        int i = 0, j = 0, k = left; // i is the left array index, j is the right array index
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        // Copy remaining elements
        while (i < n1) {
            arr[k++] = L[i++];
        }

        while (j < n2) {
            arr[k++] = R[j++];
        }
    }
}

Code Explanation

The above code implements the Merge Sort algorithm. Looking at each part:

• main method: Initializes the array and calls the merge sort method to output the sorted result.
• mergeSort method: Recursively sorts the given array by dividing it in half.
• merge method: Merges two sorted arrays into a single sorted array.

Conclusion

Merge Sort is a stable sorting algorithm suitable for sorting large amounts of data. By implementing it in Java, we have enhanced our understanding of the code and laid the foundation for practical programming applications. We hope you learn how to effectively sort complex data through the Merge Sort algorithm.

Problem Solving and Testing

Try various test cases using the Merge Sort implemented in Java. For example, test sorted arrays, reverse-sorted arrays, and arrays with duplicate elements to verify the characteristics of Merge Sort.

Applications and Practice Problems

Use Merge Sort to solve the following problems:

• Write a program to sort the given array after removing duplicate values.
• Generate an array of random numbers, sort it with Merge Sort, and print the results.

Through such practice, you can enhance your understanding of Merge Sort and improve your Java coding skills.