Merge Sort in Descending Order in Java

Author:

Merge Sort is a divide-and-conquer sorting algorithm that works by dividing an unsorted list into smaller sublists, sorting those sublists, and then merging them back together in the correct order. In this post, we will implement the Merge Sort algorithm to sort an array of integers in descending order. 

Step-by-step Implementation and Explanation 

Divide: Split the unsorted list into n sublists, each containing one element. 

Conquer: Recursively sort the sublists. 

Combine: Merge the sorted sublists to produce the final sorted list.

Java Program to Implement Merge Sort in Descending Order


public class MergeSortDescending {
    
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        
        System.out.println("Unsorted array:");
        printArray(arr);
        
        mergeSort(arr, 0, arr.length - 1);
        
        System.out.println("\nSorted array in descending order:");
        printArray(arr);
    }
    
    // Main function to sort array using merge sort
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // Find the middle point
            int middle = (left + right) / 2;
            
            // Sort first and second halves
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);
            
            // Merge the sorted halves
            merge(arr, left, middle, right);
        }
    }

    // Merging function
    public static void merge(int[] arr, int left, int middle, int right) {
        int size1 = middle - left + 1;
        int size2 = right - middle;
        
        int[] leftArray = new int[size1];
        int[] rightArray = new int[size2];
        
        // Copy data to temporary arrays
        for (int i = 0; i < size1; i++)
            leftArray[i] = arr[left + i];
        for (int j = 0; j < size2; j++)
            rightArray[j] = arr[middle + 1 + j];
        
        // Initial indices of left and right sub-arrays
        int i = 0, j = 0;
        
        // Initial index of merged sub-array
        int k = left;
        while (i < size1 && j < size2) {
            // Descending order condition
            if (leftArray[i] >= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }
        
        // Copy remaining elements of leftArray
        while (i < size1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }
        
        // Copy remaining elements of rightArray
        while (j < size2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }
    
    // Utility function to print the array
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output: 

Unsorted array:
12 11 13 5 6 7

Sorted array in descending order:
13 12 11 7 6 5

Explanation of the Code: 

mergeSort Function: This is a recursive function that sorts the left and right halves of the array. The array is divided using the middle index. 

merge Function: This function merges two halves of the array in descending order. Two temporary arrays, leftArray, and rightArray, are created to hold the two halves to be merged. 

Condition for Descending Order: Inside the merge function, while merging, the condition if (leftArray[i] >= rightArray[j]) ensures that the elements are placed in descending order in the merged array. 

printArray Function: This is a utility function to print the elements of the array. 

Merge Sort is a stable and efficient sorting algorithm with a time complexity of O(n log n). The above code can be modified to handle different data types and custom comparison logic. The key idea is the recursive merge process that builds the sorted array in the desired order.

Comments

Post a Comment

Leave Comment