# 1. Introduction

In this blog post, we will learn how to write a Python program to sort an array of integers in a Descending Order using the Merge Sort algorithm.

Merge Sort is a divide-and-conquer algorithm that splits a list into two halves, sorts them, and then merges them back together in the correct order. In this implementation, we will modify the standard merge sort algorithm to sort the elements in descending order.

# 2. Program Overview

1. merge_sort(): Main function that implements the recursive merge sort.

2. merge(): Helper function to merge two halves in descending order.

3. A sample list is provided to test and demonstrate the sorting algorithm.

# 3. Code Program

``````def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m

# Create temporary arrays
L =  * n1
R =  * n2

# Copy data to temp arrays L[] and R[]
for i in range(n1):
L[i] = arr[l + i]

for j in range(n2):
R[j] = arr[m + 1 + j]

# Merge the temp arrays back into arr[l..r]
i = 0     # Initial index of first subarray
j = 0     # Initial index of second subarray
k = l     # Initial index of merged subarray

while i < n1 and j < n2:
if L[i] >= R[j]:  # Modification for descending order
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

# Copy the remaining elements of L[], if there are any
while i < n1:
arr[k] = L[i]
i += 1
k += 1

# Copy the remaining elements of R[], if there are any
while j < n2:
arr[k] = R[j]
j += 1
k += 1

def merge_sort(arr, l, r):
if l < r:
# Find the middle point
m = (l + (r - 1)) // 2

# Sort first and second halves
merge_sort(arr, l, m)
merge_sort(arr, m + 1, r)
merge(arr, l, m, r)

# Driver code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print("Given array is:", arr)

merge_sort(arr, 0, len(arr) - 1)
print("\nSorted array in descending order is:", arr)
``````

### Output:

```Given array is: [12, 11, 13, 5, 6, 7]

Sorted array in descending order is: [13, 12, 11, 7, 6, 5]
```

# 4. Step By Step Explanation

1. merge(): This function takes an array and its indices (left, middle, right) as arguments. It creates two temporary arrays L[] and R[], copies the data, and merges them back in descending order.

2. merge_sort(): The main recursive function that divides the list into two halves using a middle point and sorts them.

3. Driver Code: This section demonstrates the merge sort algorithm using a sample list.

The advantage of Merge Sort is that it has a consistent O(n log n) time complexity, making it more predictable in performance compared to algorithms like Quick Sort.