Merge Sort in Ascending Order in Java

Author:
Merge sort, a divide-and-conquer algorithm, is known for its consistent O(n log n) time complexity. By recursively splitting an array into halves, sorting the individual halves, and then merging them, this algorithm guarantees a sorted output. In this blog post, we will go through the mechanism of Merge Sort and demonstrate how to sort an array in ascending order using Java.

Java Program for Merge Sort in Ascending Order


public class MergeSortAscending {
    
    public static void main(String[] args) {
        // Sample array of numbers to be sorted
        int[] numbers = {38, 27, 43, 3, 9, 82, 10};

        // Sort the array using Merge Sort
        mergeSort(numbers, 0, numbers.length);

        // Display the sorted array
        System.out.println("Sorted array in ascending order:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }

    /**
     * Recursively sorts the array using the merge sort algorithm.
     *
     * @param arr The array to be sorted.
     * @param start The starting index of the portion to be sorted.
     * @param end The ending index of the portion to be sorted.
     */
    public static void mergeSort(int[] arr, int start, int end) {
        if (end - start < 2) {
            return;
        }
        
        // Calculate the middle index
        int mid = (start + end) / 2;

        // Divide and recursively sort both halves
        mergeSort(arr, start, mid);
        mergeSort(arr, mid, end);

        // Merge the two sorted halves
        merge(arr, start, mid, end);
    }

    /**
     * Merges two sorted sections of the array.
     *
     * @param arr The array with segments to merge.
     * @param start The starting index of the first segment.
     * @param mid The ending index of the first segment and starting index of the second.
     * @param end The ending index of the second segment.
     */
    public static void merge(int[] arr, int start, int mid, int end) {
        if (arr[mid - 1] <= arr[mid]) {
            return;
        }
        
        int i = start;
        int j = mid;
        int tempIndex = 0;
        int[] temp = new int[end - start];

        // Actual merging process
        while (i < mid && j < end) {
            temp[tempIndex++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }

        System.arraycopy(arr, i, arr, start + tempIndex, mid - i);
        System.arraycopy(temp, 0, arr, start, tempIndex);
    }
}

Output: 

Sorted array in ascending order:
3 9 10 27 38 43 82

Step-by-Step Explanation: 

Initialization: The program begins with a sample integer array numbers. Our aim is to sort this array in ascending order. 

Conceptual Overview: Merge sort's main idea is to divide the array into two halves, sort them, and merge them in a sorted manner. This process is recursive, meaning the halves are further divided until they're of length 1 or 0. 

Recursive Splitting: The function mergeSort handles the recursive sorting mechanism. If the section's length is less than 2, it's already sorted. Otherwise, it calculates a mid-point and recursively sorts the left and right halves of the section. 

Merging Sorted Halves: The merge function is responsible for the merging process. It compares elements of both sections and places the smallest value in a temporary array. If either section gets exhausted, the remaining elements of the other section are copied over. 

Result: The sorted values from the temporary array are copied back into the main array, giving us a sorted segment. 

Display: The sorted array is then displayed on the console. 

Merge sort's magic lies in its splitting and merging, making it a preferred algorithm for larger datasets. The above program and explanation should equip you to effectively implement and understand the Merge Sort in Java for ascending order sorting. Happy coding!

Comments

Post a Comment

Leave Comment