Create a merged sorted array with two arrays simultaneously (JAVA)

Question

I have 2 arrays:

int[] num1 = {2, 4, 5, 1};
int[] num2 = {3, 6};

The objective is to create a merged sorted array like this

1 2 3 4 5 6

However, there are catches:

no arrays class, or any built-in classes (e.g. java.util.*)
they have to be sorted simultaneously (which means you cannot merge then sort, Sort both of them to one array in one go)

This feels a bit too crazy for an algorithms question. Any ideas?

You can use `insertion sort` https://www.geeksforgeeks.org/insertion-sort/ You can show what you have tried to get better help. — ajayg2808, Oct 04 '22 at 17:26
You can't do it without classes in Java. It is impossible. So you need to be more specific. And you should include your attempt at solving this yourself. — WJS, Oct 04 '22 at 17:27
You need to clarify where any of these arrays is sorted or not? — Alexander Ivanchenko, Oct 06 '22 at 12:38

score 0 · Answer 1 · answered Oct 06 '22 at 18:32

Assuming that you have two arrays sorted and unsorted, you can merge them together and sort simultaneously using the classic Insertion sort algorithm.

The problem can be tacked in the following steps:

Create a new array that would contain the final result. Its size should be equal to the sum of lengths of the two given arrays.
Copy the elements from the given sorted array to the very beginning of the resulting array.
Apply the Insertion sort by iterating over the given unsorted array. The first index which should consider for inserting the first element from the unsorted array to the resulting array would be equal to the length of the sorted array (this index denoted as boundary in the code below). In case if a new element (denoted as next) is less than the previous element in the sorted part of the array, we need to shift the previous element until the proper place to insert the new element in not found.

The implementation might look like that:

 public static int[] mergeSortedAndUnsorted(int[] sorted, int[] unsorted) {
    int[] result = new int[sorted.length + unsorted.length];
    
    for (int i = 0; i < sorted.length; i++) result[i] = sorted[i];
    
    int boundary = sorted.length;
    
    for (int next: unsorted) {
        int posToInsert = boundary;
        while (posToInsert > 0 && result[posToInsert - 1] > next) {
            result[posToInsert] = result[posToInsert - 1];
            posToInsert--;
        }
        result[posToInsert] = next;
        boundary++;
    }
    return result;
}

main()

public static void main(String[] args) {
    int[] unsorted = {2, 4, 5, 1};
    int[] sorted = {3, 6};
    
    // Merging and printing the result, utility method Arrays.toString() is unrelated to logic of the algorithm and is being used for demo purposes 
    System.out.println(Arrays.toString(mergeSortedAndUnsorted(sorted, unsorted)));
}

Output:

[1, 2, 3, 4, 5, 6]

Create a merged sorted array with two arrays simultaneously (JAVA)

1 Answers1