0

I have an array A with values: {10, 12, 6, 14, 7} and I have an array B with values: {1, 8, 2}
I have sorted the array B in an ascending order and then combined both the arrays in a new array C as shown in the following code -

static void Main()
{
    int A[] = {10, 12, 6, 14, 7};
    int B[] = {1, 8, 2};

    Array.Sort(B);
    var myList = new List<int>();
    myList.AddRange(A);
    myList.AddRange(B);
    int[] C = myList.ToArray();

    //need values in this order: 10, 1, 12, 2, 8, 6, 14, 7
}

Now I wanna sort the array C this way: 10, 1, 12, 2, 8, 6, 14, 7

The smaller values should be between the larger values, for ex: 1 is between 10 and 12, 2 is between 12 and 8, 6 is between 8 and 14, so on and so forth.

How can I do this in C#?

If recursion is needed, how can I add it to the code?

atiyar
  • 7,762
  • 6
  • 34
  • 75
Keith Clay
  • 11
  • If the only criteria you have is that the smaller numbers have to be between the larger numbers then why is it necessary that it has to be [10, 1, 12, 2, 8, 6, 14, 7] in your example? Technically, [.. 1, 12, 2 ..] violates this requirement. We need further clarifications. – Omar Abdel Bari Jan 30 '21 at 23:29
  • Does this answer your question? [Is there an easy way to merge two ordered sequences using LINQ?](https://stackoverflow.com/questions/9807701/is-there-an-easy-way-to-merge-two-ordered-sequences-using-linq) – Charlieface Jan 30 '21 at 23:43
  • Can we have more sample input and output if there is an exact output like above that you are looking for? – Omar Abdel Bari Feb 01 '21 at 04:43

1 Answers1

0

What I understood from your example is that you are trying to alternate between large and small values such that the small value is always smaller than the number to the left and the right. I wrote an algorithm below to do that however it does not yield the exact same results you requested. However I believe it does meet the requirement.

The straggling 7 is considered the next smallest number in the sequence but there is no number that follows it. Based on your example it appears that is allowed.

To Invoke

    int[] A = { 10, 12, 6, 14, 7 };
    int[] B = { 1, 8, 2 };

    var result = Sort(A, B);

Sort Method

    public static int[] Sort(int[] A, int[] B)
    {
        var result = new int[A.Length + B.Length];
        var resultIndex = 0;

        Array.Sort(A);
        Array.Sort(B);

        //'Pointer' for lower index, higher index
        var aLeft = 0;
        var aRight = A.Length-1;

        var bLeft = 0;
        var bRight = B.Length - 1;

        //When Items remain in both arrays
        while (aRight >= aLeft && bRight >= bLeft)
        {
            //Add smallest
            if (resultIndex % 2 > 0)
            {
                if (A[aLeft] < B[bLeft])
                    result[resultIndex++] = A[aLeft++];
                else
                    result[resultIndex++] = B[bLeft++];

            }
            //Add largest
            else
            {
                if (A[aRight] > B[bRight])
                    result[resultIndex++] = A[aRight--];
                else
                    result[resultIndex++] = B[bRight--];
            }
        }

        //When items only in array A
        while (aRight >= aLeft)
        {
            //Add smallest
            if (resultIndex % 2 > 0)
                result[resultIndex++] = A[aLeft++];
            //Add largest
            else
                result[resultIndex++] = A[aRight--];

        }


        //When items remain only in B
        while (bRight >= bLeft)
        {
            //Add smallest
            if (resultIndex % 2 > 0)
                result[resultIndex++] = B[bLeft++];
            //Add largest
            else
                result[resultIndex++] = B[bRight--];

        }
        return result;
    }

Result

[14, 1, 12, 2, 10, 6, 8, 7]

Omar Abdel Bari
  • 934
  • 9
  • 17