Merge Sort in Ascending Order in Java

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (176K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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!

Related Java Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in Java
2. Bubble Sort in Descending Order in Java
3. Selection Sort in Ascending Order in Java
4. Selection Sort in Descending Order in Java
5. Insertion Sort in Ascending Order in Java
6. Insertion Sort in Descending Order in Java
7. Merge Sort in Ascending Order in Java
8. Merge Sort in Descending Order in Java
9. Quick Sort in Ascending Order in Java
10. Quick Sort in Descending Order in Java