Merge Two Sorted Arrays In Descending Order Java

Merging two sorted arrays is a common programming challenge that often requires specific strategies to ensure efficiency and correctness. When the goal is to combine two arrays, already sorted in ascending order, into a single array sorted in descending order, a thoughtful approach is essential. In this article, you will learn how to effectively merge two sorted arrays in descending order using various Java techniques.

Problem Statement

The problem involves taking two arrays, each independently sorted in ascending order, and producing a new array that contains all elements from both input arrays, sorted in descending order. This task is crucial in scenarios where data from multiple sources needs to be aggregated and presented with the most significant or latest values appearing first. A naive approach of simply concatenating and then sorting the combined array can be inefficient for larger datasets.

Example

Consider two input arrays, arr1 and arr2, already sorted in ascending order:

arr1 = {1, 3, 5, 7} arr2 = {2, 4, 6, 8}

The desired output, a merged array sorted in descending order, would be:

mergedArray = {8, 7, 6, 5, 4, 3, 2, 1}

Background & Knowledge Prerequisites

To understand the solutions presented in this article, readers should have a basic understanding of:

• Java Array Basics: How to declare, initialize, and manipulate arrays.
• Looping Constructs: for and while loops for iterating through arrays.
• Conditional Statements: if-else structures for comparison logic.
• ArrayList (Optional but useful): Understanding dynamic arrays and their operations.
• Sorting Concepts: Basic knowledge of how sorting algorithms work, even if not implementing one from scratch.

Use Cases or Case Studies

Merging sorted arrays in descending order finds applications in various real-world scenarios:

• Combining Search Results: When results from multiple search engines or databases (each providing sorted results) need to be merged and presented to the user with the most relevant (highest-ranked) items first.
• Financial Data Aggregation: Merging transaction logs or stock prices from different periods or sources, where the latest or highest values are of primary interest.
• Sensor Data Processing: Combining time-series data from multiple sensors, prioritizing the most recent readings or highest observed values.
• Competitive Programming: Many algorithmic problems involve optimizing operations on sorted data structures, making efficient merging a valuable skill.
• Log File Analysis: Consolidating log entries from various system components, displaying the most recent or critical events first for quick review.

Solution Approaches

Here are a few ways to merge two sorted arrays in descending order in Java. We will detail three key approaches.

Approach 1: Combine and Sort

This approach is straightforward: first, combine all elements from both arrays into a single new array, and then sort this combined array in descending order.

• One-line summary: Concatenate the two arrays and then sort the resulting array in reverse order.

// Merge Two Sorted Arrays - Combine and Sort
import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};

        // Step 1: Calculate the total length of the new array
        int totalLength = arr1.length + arr2.length;
        
        // Step 2: Create a new array to hold all elements
        // Using Integer array for Collections.sort with reverseOrder
        Integer[] mergedArray = new Integer[totalLength]; 
        
        // Step 3: Copy elements from arr1 to mergedArray
        for (int i = 0; i < arr1.length; i++) {
            mergedArray[i] = arr1[i];
        }
        
        // Step 4: Copy elements from arr2 to mergedArray, starting after arr1's elements
        for (int i = 0; i < arr2.length; i++) {
            mergedArray[arr1.length + i] = arr2[i];
        }
        
        // Step 5: Sort the merged array in descending order
        Arrays.sort(mergedArray, Collections.reverseOrder());
        
        // Step 6: Print the merged array
        System.out.println("Merged Array (Combine and Sort): " + Arrays.toString(mergedArray));
    }
}

Run

Sample Output:

Merged Array (Combine and Sort): [8, 7, 6, 5, 4, 3, 2, 1]

Stepwise Explanation:

1. Determine Length: Calculate the total size required for the new array by summing the lengths of arr1 and arr2.
2. Create Array: Initialize an Integer array (not int[]) of this totalLength. Collections.reverseOrder() requires an array of Object types (like Integer[]) rather than primitive int[].
3. Copy arr1: Iterate through arr1 and copy all its elements into the mergedArray.
4. Copy arr2: Iterate through arr2 and copy its elements into the mergedArray, starting at the index immediately following the last element of arr1.
5. Sort Descending: Use Arrays.sort() along with Collections.reverseOrder() to sort the entire mergedArray in descending order.
6. Print Result: Display the final sorted array.

Approach 2: Two-Pointer Approach (Optimized)

This approach leverages the fact that both input arrays are already sorted to perform the merge efficiently without a full sort at the end. To get a descending order result, we compare elements from the *end* of the ascending input arrays and place the larger element into the *end* of the result array.

• One-line summary: Use three pointers to iteratively compare the largest remaining elements from both input arrays and place them into the result array from its end.

// Merge Two Sorted Arrays - Two-Pointer Approach
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};

        // Step 1: Calculate the total length for the new array
        int totalLength = arr1.length + arr2.length;
        int[] mergedArray = new int[totalLength];

        // Step 2: Initialize pointers
        // p1 points to the last element of arr1
        int p1 = arr1.length - 1; 
        // p2 points to the last element of arr2
        int p2 = arr2.length - 1; 
        // p3 points to the last position of mergedArray (where the largest element goes)
        int p3 = totalLength - 1; 

        // Step 3: Iterate while both pointers p1 and p2 are valid
        while (p1 >= 0 && p2 >= 0) {
            if (arr1[p1] >= arr2[p2]) {
                mergedArray[p3] = arr1[p1];
                p1--;
            } else {
                mergedArray[p3] = arr2[p2];
                p2--;
            }
            p3--;
        }

        // Step 4: Add any remaining elements from arr1 (if arr2 was exhausted first)
        while (p1 >= 0) {
            mergedArray[p3] = arr1[p1];
            p1--;
            p3--;
        }

        // Step 5: Add any remaining elements from arr2 (if arr1 was exhausted first)
        while (p2 >= 0) {
            mergedArray[p3] = arr2[p2];
            p2--;
            p3--;
        }
        
        // Step 6: Print the merged array
        System.out.println("Merged Array (Two-Pointer): " + Arrays.toString(mergedArray));
    }
}

Run

Sample Output:

Merged Array (Two-Pointer): [8, 7, 6, 5, 4, 3, 2, 1]

Stepwise Explanation:

1. Initialize: Create a mergedArray of the combined size. Initialize three pointers:

• p1: points to the last element of arr1.
• p2: points to the last element of arr2.
• p3: points to the last position of mergedArray (where the largest element will be placed).

1. Compare and Place (Main Loop): While both p1 and p2 are valid (i.e., not less than 0):

• Compare arr1[p1] and arr2[p2].
• The larger of the two is placed into mergedArray[p3].
• Decrement the pointer of the array from which the element was taken (p1 or p2).
• Decrement p3 to move to the next position in mergedArray.

1. Handle Remaining arr1: After the main loop, one of the input arrays might still have elements left. If arr1 has remaining elements (p1 >= 0), copy them directly into mergedArray from p3 downwards.
2. Handle Remaining arr2: Similarly, if arr2 has remaining elements (p2 >= 0), copy them directly.
3. Print Result: Display the final sorted array.

Approach 3: Using ArrayList and Collections.sort

This approach leverages Java's dynamic list capabilities and its built-in sorting utility, offering a balance between simplicity and efficiency, especially for scenarios where array resizing is not a concern.

• One-line summary: Add all elements to an ArrayList, then sort the list in descending order.

// Merge Two Sorted Arrays - ArrayList and Collections.sort
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};

        // Step 1: Create an ArrayList to hold all elements
        List<Integer> mergedList = new ArrayList<>();

        // Step 2: Add all elements from arr1 to the list
        for (int num : arr1) {
            mergedList.add(num);
        }

        // Step 3: Add all elements from arr2 to the list
        for (int num : arr2) {
            mergedList.add(num);
        }

        // Step 4: Sort the ArrayList in descending order
        Collections.sort(mergedList, Collections.reverseOrder());
        
        // Step 5: Print the merged list
        System.out.println("Merged List (ArrayList & Collections.sort): " + mergedList);
        
        // Optional: Convert back to int[] array if needed
        // int[] finalMergedArray = mergedList.stream().mapToInt(Integer::intValue).toArray();
        // System.out.println("Merged Array (converted from List): " + Arrays.toString(finalMergedArray));
    }
}

Run

Sample Output:

Merged List (ArrayList & Collections.sort): [8, 7, 6, 5, 4, 3, 2, 1]

Stepwise Explanation:

1. Create ArrayList: Initialize an ArrayList of Integer to store the combined elements.
2. Add arr1 Elements: Iterate through arr1 and add each element to mergedList.
3. Add arr2 Elements: Iterate through arr2 and add each element to mergedList.
4. Sort Descending: Use Collections.sort() with Collections.reverseOrder() to sort the mergedList in descending order.
5. Print Result: Display the final sorted ArrayList. An optional step is included to show how to convert it back to a primitive int[] if required.

Conclusion

Merging two already sorted arrays into a single array sorted in descending order can be achieved through several methods in Java. While combining all elements and then performing a full sort is a straightforward approach, the two-pointer method offers a significantly more efficient solution by leveraging the pre-sorted nature of the input arrays. The ArrayList and Collections.sort method provides a flexible and concise alternative, especially when dealing with dynamic data sizes. The choice of method depends on performance requirements, memory constraints, and the specific context of the application.

Summary

• Problem: Merge two ascending-sorted arrays into one descending-sorted array.
• Approach 1 (Combine and Sort):
• Concatenate both arrays into a new Integer[].
• Use Arrays.sort(array, Collections.reverseOrder()) to sort it descending.
• Simple, but less efficient for large arrays due to the full sort.
• Approach 2 (Two-Pointer):
• Initialize three pointers: p1 for arr1 (end), p2 for arr2 (end), p3 for result array (end).
• Compare arr1[p1] and arr2[p2], placing the larger into mergedArray[p3].
• Decrement corresponding p1/p2 and p3.
• Handle any remaining elements.
• Highly efficient (linear time complexity).
• Approach 3 (ArrayList and Collections.sort):
• Add all elements from both arrays into an ArrayList.
• Use Collections.sort(list, Collections.reverseOrder()) to sort the list descending.
• Offers dynamic sizing and conciseness, good for flexible scenarios.