Merging 2 sorted arrays

Merging 2 sorted arrays:

  • You are given two sorted arrays

    Example: 

      a = [2.5, 3.5, 6.4, 7.5]    
  b = [1.1, 8.9, 9.2]

  • Design an efficient algorithm to combine (= merge) the 2 sorted arrays into one single sorted array

    Example: 

      a = [2.5, 3.5, 6.4, 7.5]    
  b = [1.1, 8.9, 9.2] 

  Output: [1.1, 2.5, 3.5, 6.4, 7.5, 8.9, 9.2]

Desiging the merge algorithm

  • We use 2 indexes i and j to point to the current elements in each array

  • The output result[] array is initially empty

    Example: 

           i=0                         j=0
        |                           |
        V                           V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]    

   Result [ ]

  • How to merge/sort the 2 sorted arrays:

    • We will repeatedly copy the smallest value from both arrays to result[]

  • Important fact that will help us merge the 2 sorted arrays:

    • The current element in each array will be the smallest value in that array

Desiging the merge algorithm

  • To find the smallest value in both arrays, we only need to compare a[i=0] and b[j=0]: 

           i=0                         j=0
        |                           |
        V                           V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]    

   Result [ ]

    Since b[j] < a[i], we copy b[j] to result[ ] and increment j: 

           i=0                              j=1
        |                                |
        V                                V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1]

Desiging the merge algorithm

  • To find the smallest value in both arrays, we only need to compare a[i=0] and b[j=1]: 

           i=0                              j=1
        |                                |
        V                                V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1]

    Since a[i] < b[j], we copy a[i] to result[ ] and increment i: 

                i=1                         j=1
             |                           |
             V                           V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5]

Desiging the merge algorithm

  • To find the smallest value in both arrays, we only need to compare a[i=1] and b[j=1]: 

                i=1                         j=1
             |                           |
             V                           V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5]

    Since a[i] < b[j], we copy a[i] to result[ ] and increment i: 

                     i=2                    j=1
                  |                      |
                  V                      V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5]

Desiging the merge algorithm

  • To find the smallest value in both arrays, we only need to compare a[i=2] and b[j=1]: 

                     i=2                    j=1
                  |                      |
                  V                      V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5]

    Since a[i] < b[j], we copy a[i] to result[ ] and increment i: 

                          i=3               j=1
                       |                 |
                       V                 V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5, 6.4]

Desiging the merge algorithm

  • To find the smallest value in both arrays, we only need to compare a[i=3] and b[j=1]: 

                          i=3               j=1
                       |                 |
                       V                 V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5, 6.4]

    Since a[i] < b[j], we copy a[i] to result[ ] and increment i: 

                             i=4            j=1
                          |              |
                          V              V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5, 6.4, 7.5]

Desiging the merge algorithm

  • Array a is exhausted:   the smallest value in both arrays is found in array b: 

                             i=4            j=1
                          |              |
                          V              V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5, 6.4, 7.5]

    Since array a is exhausted, we copy b[j] to result[ ] and increment j: 

                             i=4                 j=2
                          |                   |
                          V                   V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5, 6.4, 7.5, 8.9]

Desiging the merge algorithm

  • Array a is exhausted:   the smallest value in both arrays is found in array b: 

                             i=5                 j=2
                          |                   |
                          V                   V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5, 6.4, 7.5, 8.9]

    Since array a is exhausted, we copy b[j] to result[ ] and increment j: 

                             i=5                    j=3
                          |                      |
                          V                      V
   a  [2.5, 3.5, 6.4, 7.5]     b  [1.1, 8.9, 9.2]      

   Result [1.1, 2.5, 3.5, 6.4, 7.5, 8.9, 9.2]

Now both arrays are exhausted and the merge algorithm terminates !

The merge algorithm to merge 2 sorted arrays

We now write the merge( ) algorithm that merges 2 sorted arrays: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both array have elements

                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else
                    result[k++] = b[j++];
	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];

        }
    }

The merge algorithm to merge 2 sorted arrays

We first define and initialize the indexes that points to the elements in the (3) arrays: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both array have elements

                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else
                    result[k++] = b[j++];
	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];

        }
    }

The merge algorithm to merge 2 sorted arrays

We repeat as long as one of the array still has an unprocessed element: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both array have elements

                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else
                    result[k++] = b[j++];
	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];

        }
    }

The merge algorithm to merge 2 sorted arrays

We must handle 3 cases: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {

	

	     case 1:  both a and b have unprocessed elements
     
	     case 2:  array a is exhausted
              
             case 3:  array b is exhausted
	 
           
            
	    
              
        }
    }

The merge algorithm to merge 2 sorted arrays

Case 1:   how to detect when both arrays have unprocessed elements: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both arrays have unprocessed elements

                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else
                    result[k++] = b[j++];

	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];
        }
    }

The merge algorithm to merge 2 sorted arrays

Case 1:   if a[i] < b[j], we copy a[i] over to result[k] and increment   i   and  k: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both arrays have unprocessed elements
                if ( a[i] < b[j] ) 
                {
	            result[k] = a[i];
                    i = i + 1;
                    k = k + 1;          
                }
	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];
        }
    }

The merge algorithm to merge 2 sorted arrays

Shorthand:   if we increase a variable by 1 after we used the variable, we can use shorthand var++: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both arrays have unprocessed elements
                if ( a[i] < b[j] ) 
                {
	            result[k] = a[i];  // Use i and k
                    i = i + 1;         // After using i, increment i by 1
                    k = k + 1;         // After using k, increment k by 1
                }
	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];
        }
    }

The merge algorithm to merge 2 sorted arrays

Shorthand:   if we increase a variable by 1 after we used the variable, we can use shorthand var++: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both arrays have unprocessed elements
                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else
                    result[k++] = b[j++];


	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];
        }
    }

The merge algorithm to merge 2 sorted arrays

Case 1:   if a[i] ≥ b[j], we copy b[j] over to result[k] and increment  j  and  k: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both arrays have unprocessed elements
                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else 
                {   result[k] = b[j];
		    k = k + 1;
		    j = j + 1;    }
	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];
        }
    }

The merge algorithm to merge 2 sorted arrays

Shorthand:   if we increase a variable by 1 after we used the variable, we can use shorthand var++: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both arrays have unprocessed elements
                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else
                    result[k++] = b[j++];


	    }
            else if ( i == a.length )     // a is empty
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];
        }
    }

The merge algorithm to merge 2 sorted arrays

Case 2:   if array a is exhausted, we copy b[j] over to result[k] and increment  j  and  k: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both arrays have unprocessed elements
                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else
                    result[k++] = b[j++];


	    }
            else if ( i == a.length )     // a is exhausted (empty)
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is empty
                result[k++] = a[i++];
        }
    }

The merge algorithm to merge 2 sorted arrays

Case 3:   if array b is exhausted, we copy a[i] over to result[k] and increment  i  and  k: 

    // merge(result, a, b): merge 2 sorted arrays a and b into array result

    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
       	    if ( i < a.length && j < b.length )
	    {  // Both arrays have unprocessed elements
                if ( a[i] < b[j] )
	            result[k++] = a[i++];
                else
                    result[k++] = b[j++];


	    }
            else if ( i == a.length )     // a is exhausted (empty)
                result[k++] = b[j++];
	    else if ( j == b.length )     // b is exhausted (empty)
                result[k++] = a[i++];
        }
    }

Test program 

    public static void main(String[] args)
    {
        double[] list1 = {1, 3, 5, 7, 8};  // Sorted
        double[] list2 = {2, 4, 6, 9};     // Sorted
        double[] r = new double[list1.length + list2.length];
        
        for(int i = 0; i < list1.length; i++)
            System.out.print(list1[i] + " ");
        System.out.println();
        
        for(int i = 0; i < list2.length; i++)
            System.out.print(list2[i] + " ");
        System.out.println();
        
        merge(r, list1, list2);

        for(int i = 0; i < r.length; i++)
            System.out.print(r[i] + " ");
        System.out.println();
    }

DEMO: demo/08-array/12-sorting/MergeArrays.java