ISC Practicals and Theory - Merge Two Sorted Arrays (OOP)

Two sorted arrays can be merged into one sorted array in a single pass using two pointers, one on each array, always copying the smaller current element. This version is written as a class: the arrays and sizes are data members, a parameterised constructor receives the two arrays, and separate methods check the order, merge and display. It accepts two integer arrays of 1 to 10 elements each, in ascending order.

Definition

If $A$ has $m$ elements and $B$ has $n$ elements, both in ascending order, the merged array $C$ has $m + n$ elements in ascending order. For example, $A = \{2, 6, 9\}$ and $B = \{3, 4\}$ give $C = \{2, 3, 4, 6, 9\}$.

• Each size must be from 1 to 10, otherwise an error message is printed.
• An array that is not in ascending order is rejected with an error message (equal neighbours such as 5 5 are allowed).
• Duplicates are all kept, and on a tie the element of A is copied first.

Algorithm

1. In main, read the sizes p and q. If either is outside 1 to 10, print an error message and stop.
2. Create the arrays x and y, read their elements and create the object with new MergeSorted(x, y, p, q). The constructor stores the arrays and sizes in a, b, m, n and creates c of size m + n.
3. Call isSorted() for both arrays. If either returns false, print an error message and stop.
4. Call merge():
   • Set i = 0, j = 0, k = 0.
   • While i < m and j < n: if a[i] <= b[j], copy a[i] to c[k] and increase i; otherwise copy b[j] to c[k] and increase j. Increase k each time.
   • Copy any elements left in a, then any elements left in b.
5. Call display() to print the elements of c.

Program

The constructor stores the data, isSorted() returns whether an array is in ascending order, merge() fills c and display() prints it. Reading the input and checking the sizes is done in main.

import java.util.Scanner;

/* class MergeSorted: holds two ascending integer arrays and merges them into one
   ascending array using the two-pointer technique (no sorting method is used) */
public class MergeSorted
{
    int a[];   // first array, in ascending order
    int b[];   // second array, in ascending order
    int c[];   // merged array
    int m;     // number of elements in a
    int n;     // number of elements in b

    /* Parameterised constructor.
       Parameters: x - first array, y - second array, p - size of x, q - size of y */
    MergeSorted(int x[], int y[], int p, int q)
    {
        a = x;
        b = y;
        m = p;
        n = q;
        c = new int[m + n];    // room for all elements of both arrays
    }

    /* Parameters: x - the array to check, size - number of elements in it.
       Returns true if the elements are in ascending order
       (equal neighbours are allowed), else false */
    boolean isSorted(int x[], int size)
    {
        for (int i = 0; i < size - 1; i++)
        {
            if (x[i] > x[i + 1])    // a smaller element after a larger one
                return false;
        }
        return true;
    }

    /* Merges a and b into c with two pointers; duplicates are all kept */
    void merge()
    {
        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)
        {
            // copy the smaller current element; on a tie take from a first
            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++];
    }

    /* Displays the merged array */
    void display()
    {
        System.out.println("Merged array:");
        for (int k = 0; k < m + n; k++)
        {
            System.out.print(c[k] + " ");
        }
        System.out.println();
    }

    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 p = sc.nextInt();
        System.out.print("Enter the size of the second array (1 to 10): ");
        int q = sc.nextInt();
        if (p < 1 || p > 10 || q < 1 || q > 10)
        {
            System.out.println("Invalid input. Size must be from 1 to 10.");
            return;
        }
        int x[] = new int[p];
        int y[] = new int[q];
        System.out.println("Enter the elements of the first array in ascending order:");
        for (int i = 0; i < p; i++)
            x[i] = sc.nextInt();
        System.out.println("Enter the elements of the second array in ascending order:");
        for (int i = 0; i < q; i++)
            y[i] = sc.nextInt();

        MergeSorted ob = new MergeSorted(x, y, p, q);
        if (!ob.isSorted(x, p) || !ob.isSorted(y, q))
        {
            System.out.println("Invalid input. Both arrays must be in ascending order.");
            return;
        }
        ob.merge();
        ob.display();
    }
}

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: p = 3, q = 2, x = {6, 8, 9}, y = {1, 2}.

Now j = 2 = n, so the first loop ends and while (i < m) copies 6, 8 and 9 to c[2], c[3] and c[4]. The merged array is 1 2 6 8 9, which matches the third 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."