Merge Sort in Descending Order in Python

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 = [0] * n1
    R = [0] * 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.

Related Python Programs on Sorting Algorithms

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