/*

Method 2 (First Sort then Merge)

​

We first sort both the given arrays separately. Then we simply merge two sorted arrays. 

​

​

​

Input : a[] = {1, 10, 5, 15}

        b[] = {20, 0, 2}

Output : Merge List :

        {0, 1, 2, 5, 10, 15, 20}

​

*/

​

using System;

public class Program

{

    static void sortedMerge(int []a, int []b, 

                     int []res, int n, int m) 

    { 

        // Sorting a[] and b[] 

        Array.Sort(a); 

        Array.Sort(b); 

        // Merge two sorted arrays into res[] 

        int i = 0, j = 0, k = 0; 

        while (i < n && j < m) 

        { 

            if (a[i] <= b[j]) 

            { 

                res[k] = a[i]; 

                i += 1; 

                k += 1; 

            }  

            else 

            { 

                res[k] = b[j]; 

                j += 1; 

                k += 1; 

            } 

        }  

        while (i < n) 

        {  

            // Merging remaining 

            // elements of a[] (if any) 

            res[k] = a[i]; 

            i += 1; 

            k += 1; 

        }  

        while (j < m) 

        { 

            // Merging remaining 

            // elements of b[] (if any) 

            res[k] = b[j]; 

            j += 1; 

            k += 1; 

        } 

    } 

    /* Driver program to test 

    above function */

    public static void Main()  

    { 

        int []a = { 10, 5, 15 }; 

        int []b = { 20, 3, 2, 12 }; 

        int n = a.Length; 

        int m = b.Length; 

        // Final merge list 

        int []res = new int[n + m]; 

        sortedMerge(a, b, res, n, m); 

        Console.Write( "Sorted merged list :"); 

        for (int i = 0; i < n + m; i++) 

            Console.Write(" " + res[i]);  

    } 

} 

​