ISC Practicals and Theory - Merge Two Sorted Arrays

Merging two sorted arrays means combining them into a single array that is also sorted. Because both inputs are already in ascending order, the merged array can be built in one pass over them, without sorting the combined data again. This program, written in the main method alone, reads two integer arrays of 1 to 10 elements each, checks that each is in ascending order, merges them with the two-pointer technique and displays the merged array.

Definition

Given an array $A$ of $m$ elements and an array $B$ of $n$ elements, both in ascending order, the merged array $C$ has $m + n$ elements and is in ascending order. Two pointers are used: i points to the smallest element of A not yet copied and j points to the smallest element of B not yet copied. The smaller of A[i] and B[j] is copied to C and its pointer moves forward.

For example, $A = \{2, 6, 9\}$ and $B = \{3, 4\}$ give $C = \{2, 3, 4, 6, 9\}$.

Assumptions made by this program:

• Each size must be from 1 to 10. A size outside this range is rejected with an error message.
• An array that is not in ascending order is rejected with an error message, because the two-pointer method only gives a sorted result for sorted inputs. Equal neighbours (for example 5 5) are allowed.
• Duplicates are all kept: if a value is present in both arrays, it appears in the merged array as many times as in both arrays together. When A[i] equals B[j], the element of A is copied first.

Algorithm

1. Read the sizes m and n of the two arrays. If either is not from 1 to 10, print an error message and stop.
2. Read the elements of a and of b.
3. Check that each array is in ascending order (equal neighbours are allowed): if a[x] > a[x + 1] or b[x] > b[x + 1] anywhere, set sorted = false. If sorted is false, print an error message and stop.
4. Create the array c of size m + n. Use three pointers: i into a, j into b and k for the next place to fill in c, all starting at 0.
5. While both arrays have elements left (i < m && j < n), copy the smaller of a[i] and b[j] to c[k] and move that pointer and k forward. On a tie, the element of a is copied first.
6. When one array is finished, copy the rest of the other array to c.
7. Print the merged array.

Program

The three while loops at the end of main do the merge: the first compares the two arrays, the other two copy what is left.

import java.util.Scanner;

/* Program MergeSorted merges two sorted arrays into one sorted array
   using the two-pointer technique (no sorting method is used) */
public class MergeSorted
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the size of the first array (1 to 10): ");
        int m = sc.nextInt();                  // number of elements in a
        System.out.print("Enter the size of the second array (1 to 10): ");
        int n = sc.nextInt();                  // number of elements in b
        if (m < 1 || m > 10 || n < 1 || n > 10)
        {
            System.out.println("Invalid input. Size must be from 1 to 10.");
            return;
        }
        int a[] = new int[m];                  // first array, in ascending order
        int b[] = new int[n];                  // second array, in ascending order
        System.out.println("Enter the elements of the first array in ascending order:");
        for (int x = 0; x < m; x++)
        {
            a[x] = sc.nextInt();
        }
        System.out.println("Enter the elements of the second array in ascending order:");
        for (int x = 0; x < n; x++)
        {
            b[x] = sc.nextInt();
        }
        boolean sorted = true;                 // stays true while both arrays are in ascending order
        for (int x = 0; x < m - 1; x++)
        {
            if (a[x] > a[x + 1])               // a smaller element after a larger one
                sorted = false;
        }
        for (int x = 0; x < n - 1; x++)
        {
            if (b[x] > b[x + 1])
                sorted = false;
        }
        if (!sorted)
        {
            System.out.println("Invalid input. Both arrays must be in ascending order.");
            return;
        }
        int c[] = new int[m + n];              // merged array
        int i = 0;                             // pointer into a
        int j = 0;                             // pointer into b
        int k = 0;                             // position to fill in c
        while (i < m && j < n)
        {
            if (a[i] <= b[j])
                c[k++] = a[i++];
            else
                c[k++] = b[j++];
        }
        while (i < m)                          // b is finished: copy the rest of a
            c[k++] = a[i++];
        while (j < n)                          // a is finished: copy the rest of b
            c[k++] = b[j++];
        System.out.println("Merged array:");
        for (k = 0; k < m + n; k++)
        {
            System.out.print(c[k] + " ");
        }
        System.out.println();
    }
}

Variable description table

Sample input and output

Enter the size of the first array (1 to 10): 4
Enter the size of the second array (1 to 10): 3
Enter the elements of the first array in ascending order:
1 4 7 10
Enter the elements of the second array in ascending order:
2 4 9
Merged array:
1 2 4 4 7 9 10 

Enter the size of the first array (1 to 10): 1
Enter the size of the second array (1 to 10): 1
Enter the elements of the first array in ascending order:
5
Enter the elements of the second array in ascending order:
3
Merged array:
3 5 

Enter the size of the first array (1 to 10): 3
Enter the size of the second array (1 to 10): 2
Enter the elements of the first array in ascending order:
6 8 9
Enter the elements of the second array in ascending order:
1 2
Merged array:
1 2 6 8 9 

Enter the size of the first array (1 to 10): 2
Enter the size of the second array (1 to 10): 2
Enter the elements of the first array in ascending order:
5 5
Enter the elements of the second array in ascending order:
5 5
Merged array:
5 5 5 5 

Enter the size of the first array (1 to 10): 3
Enter the size of the second array (1 to 10): 3
Enter the elements of the first array in ascending order:
1 9 4
Enter the elements of the second array in ascending order:
2 3 5
Invalid input. Both arrays must be in ascending order.

Enter the size of the first array (1 to 10): 0
Enter the size of the second array (1 to 10): 3
Invalid input. Size must be from 1 to 10.

Dry run

Input: m = 4, n = 3, a = {1, 4, 7, 10}, b = {2, 4, 9}.

Now j = 3 = n, so the first loop ends. The loop while (i < m) copies the remaining a[3] = 10 to c[6]. The merged array is 1 2 4 4 7 9 10, which matches the output of the first sample run.

Variations

1. Descending order "Merge two arrays that are in descending order into one array in descending order."
2. Without duplicates "Merge two sorted arrays so that a value present in both appears only once."
3. Unsorted inputs "Merge two unsorted arrays and then sort the merged array using a sorting technique."
4. Alternate merge "Merge two arrays by taking one element from each array in turn."