### Merge Sort in Descending Order in Java

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.