Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Descending Merge Sort

Problem Statement

Write a Java program that modifies the Merge Sort implementation to sort an array of integers in descending order (largest to smallest) by adjusting the comparison logic in the merge step. The program should test the implementation with arrays of different sizes (e.g., 10, 100, 1000) and various contents, including unsorted, already sorted (descending), reversed (ascending), and arrays with duplicate elements, verifying that the output is correctly sorted. Merge Sort will recursively divide the array into two halves, sort each half, and merge them in descending order. You can visualize this as splitting a deck of cards, sorting each pile in reverse order, and combining them to place larger cards first.

Input:

  • An array of integers to be sorted in descending order. Output: The sorted array (in descending order) and a string representation of the input and sorted arrays for verification. Constraints:
  • The array length n is between 0 and 10^5.
  • Array elements are integers in the range [-10^9, 10^9]. Example:
  • Input: array = [64, 34, 25, 12, 22]
  • Output:
    • Input Array: [64, 34, 25, 12, 22]
    • Sorted Array: [64, 34, 25, 22, 12]
  • Explanation: Merge Sort divides, sorts, and merges to produce a descending order array.
  • Input: array = [5, 4, 3]
  • Output:
    • Input Array: [5, 4, 3]
    • Sorted Array: [5, 4, 3]
  • Explanation: Already sorted in descending order, remains unchanged.

Pseudocode

FUNCTION mergeSortDescending(arr, left, right)
    IF left < right THEN
        SET mid to floor((left + right) / 2)
        CALL mergeSortDescending(arr, left, mid)
        CALL mergeSortDescending(arr, mid + 1, right)
        CALL mergeDescending(arr, left, mid, right)
    ENDIF
ENDFUNCTION

FUNCTION mergeDescending(arr, left, mid, right)
    SET n1 to mid - left + 1
    SET n2 to right - mid
    CREATE leftArr as array of size n1
    CREATE rightArr as array of size n2
    FOR i from 0 to n1-1
        SET leftArr[i] to arr[left + i]
    ENDFOR
    FOR i from 0 to n2-1
        SET rightArr[i] to arr[mid + 1 + i]
    ENDFOR
    SET i to 0, j to 0, k to left
    WHILE i < n1 AND j < n2
        IF leftArr[i] >= rightArr[j] THEN
            SET arr[k] to leftArr[i]
            INCREMENT i
        ELSE
            SET arr[k] to rightArr[j]
            INCREMENT j
        ENDIF
        INCREMENT k
    ENDWHILE
    WHILE i < n1
        SET arr[k] to leftArr[i]
        INCREMENT i
        INCREMENT k
    ENDWHILE
    WHILE j < n2
        SET arr[k] to rightArr[j]
        INCREMENT j
        INCREMENT k
    ENDWHILE
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of input arrays with different sizes
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        CALL mergeSortDescending(copy, 0, length-1)
        PRINT input array, sorted array
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define mergeSortDescending: a. If left < right, divide array into two halves at mid. b. Recursively sort left half (left to mid) and right half (mid+1 to right). c. Merge sorted halves using mergeDescending.
  2. Define mergeDescending: a. Create temporary arrays for left and right halves. b. Compare elements, prioritizing larger ones (leftArr[i] >= rightArr[j]) to merge in descending order. c. Copy remaining elements from either half.
  3. Define toString: a. Convert array to a string, limiting output for large arrays.
  4. In main, test with: a. Small unsorted array (n=10). b. Small sorted array (descending, n=10). c. Small reversed array (ascending, n=10). d. Medium array with duplicates (n=100). e. Large unsorted array (n=1000). f. Empty array (n=0).

Java Implementation

import java.util.*;

public class DescendingMergeSort {
    // Performs Merge Sort in descending order
    public void mergeSortDescending(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // Avoid overflow
            mergeSortDescending(arr, left, mid);
            mergeSortDescending(arr, mid + 1, right);
            mergeDescending(arr, left, mid, right);
        }
    }

    // Merges two sorted subarrays in descending order
    private void mergeDescending(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArr[i] = arr[mid + 1 + i];
        }

        // Merge in descending order
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] >= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        int limit = Math.min(arr.length, 10); // Limit output for large arrays
        for (int i = 0; i < limit; i++) {
            result.append(arr[i]);
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            result.append("]");
        }
        return result.toString();
    }

    // Generates random array for testing
    private int[] generateRandomArray(int n) {
        Random rand = new Random(42); // Fixed seed for reproducibility
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(2001) - 1000; // [-1000, 1000]
        }
        return arr;
    }

    // Generates sorted array (descending) for testing
    private int[] generateSortedDescending(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = n - i;
        }
        return arr;
    }

    // Generates array with duplicates
    private int[] generateDuplicatesArray(int n) {
        Random rand = new Random(42);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(10); // Limited range for duplicates
        }
        return arr;
    }

    // Helper class for test cases
    static class TestCase {
        int[] arr;
        String description;

        TestCase(int[] arr, String description) {
            this.arr = arr;
            this.description = description;
        }
    }

    // Main method to test descending Merge Sort
    public static void main(String[] args) {
        DescendingMergeSort sorter = new DescendingMergeSort();

        // Test cases
        TestCase[] testCases = {
            new TestCase(sorter.generateRandomArray(10), "Small unsorted (n=10)"),
            new TestCase(sorter.generateSortedDescending(10), "Small sorted descending (n=10)"),
            new TestCase(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, "Small reversed (ascending, n=10)"),
            new TestCase(sorter.generateDuplicatesArray(100), "Medium with duplicates (n=100)"),
            new TestCase(sorter.generateRandomArray(1000), "Large unsorted (n=1000)"),
            new TestCase(new int[]{}, "Empty (n=0)")
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
            int[] arr = testCases[i].arr.clone(); // Copy to preserve original
            System.out.println("Input Array: " + sorter.toString(arr));
            sorter.mergeSortDescending(arr, 0, arr.length - 1);
            System.out.println("Sorted Array: " + sorter.toString(arr) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: Small unsorted (n=10)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628]
Sorted Array: [727, 648, 374, 360, 304, 289, -333, -628, -766, -767]

Test case 2: Small sorted descending (n=10)
Input Array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Sorted Array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Test case 3: Small reversed (ascending, n=10)
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sorted Array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Test case 4: Medium with duplicates (n=100)
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Sorted Array: [9, 9, 9, 9, 8, 8, 8, 8, 8, 8, ...]

Test case 5: Large unsorted (n=1000)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Sorted Array: [976, 966, 964, 960, 958, 955, 953, 952, 951, 946, ...]

Test case 6: Empty (n=0)
Input Array: []
Sorted Array: []

Explanation:

  • Test case 1: Unsorted array (n=10) is sorted in descending order.
  • Test case 2: Already sorted in descending order (n=10), remains unchanged.
  • Test case 3: Ascending array (n=10) is sorted into descending order.
  • Test case 4: Medium array with duplicates (n=100) is sorted, preserving duplicates.
  • Test case 5: Large unsorted array (n=1000) is sorted in descending order.
  • Test case 6: Empty array (n=0) remains empty.

How It Works

  • mergeSortDescending:
    • Recursively divides the array into two halves until each subarray has one element.
    • Calls mergeDescending to combine sorted subarrays in descending order.
  • mergeDescending:
    • Creates temporary arrays for left and right halves.
    • Merges elements, prioritizing larger ones (leftArr[i] >= rightArr[j]), ensuring stability.
    • Copies remaining elements from either half.
  • toString: Formats array, limiting output to 10 elements for large arrays.
  • generateRandomArray: Creates an array with random integers in [-1000, 1000].
  • generateSortedDescending: Creates a descending array [n, n-1, ..., 1].
  • generateDuplicatesArray: Creates an array with values in [0, 9] for duplicates.
  • Example Trace (Test case 1):
    • Divide: [727, -333, 648, 374, -767] → [727, -333, 648] and [374, -767].
    • Divide: [727, -333, 648] → [727] and [-333, 648]; [374, -767] → [374] and [-767].
    • Divide: [-333, 648] → [-333] and [648].
    • Merge: [-333], [648] → [648, -333].
    • Merge: [727], [648, -333] → [727, 648, -333].
    • Merge: [374], [-767] → [374, -767].
    • Merge: [727, 648, -333], [374, -767] → [727, 648, 374, -333, -767].
  • Main Method: Tests small, medium, and large arrays with various contents.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
mergeSortDescendingO(n log n)O(n)
mergeDescendingO(n)O(n)
toStringO(n)O(n)
generateRandomArrayO(n)O(n)
generateSortedDescendingO(n)O(n)
generateDuplicatesArrayO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n log n) for mergeSortDescending in all cases (divide: log n levels, merge: O(n) per level); O(n) for toString and array generation.
  • Space complexity: O(n) for mergeSortDescending (temporary arrays); O(n) for toString and array generation (string builder and arrays).
  • Descending order does not affect Merge Sort’s complexity.

✅ Tip: Modify Merge Sort for descending order by changing the merge comparison to prioritize larger elements (>=). Test with various array sizes to verify correctness across inputs.

⚠ Warning: Use >= in the merge step to ensure stability for duplicates. Clone input arrays to preserve the original order for display.