Сортировка: вариации на тему (продолжение)

Опубликовано Sep 24, 2012 в Массивы и строки | 4 коммент.

, ,

Сортировка: вариации на тему (продолжение)

Из комментария к предыдущему посту про сортировку.
Есть задачка поинтересней – как слить два уже отсортированных массива, сохранив порядок сортировки, не вызывая при этом Sort/OrderBy ни в каком виде? И сложность хочется линейную.

Обратите внимание. Эта задача не тождественна задаче из поста /archives/1018, так как в данном варианте слияние происходит в новый массив – размер буфера здесь равен сумме размерностей исходных массивов.

Вот решение.

        public static int[] merge(int[] A, int[] B)
        {
            int[] result = new int[A.Length + B.Length];
            int aIndex = 0;
            int bIndex = 0;
            while (aIndex + bIndex != result.Length)
            {
                if (aIndex == A.Length)
                {
                    result[aIndex + bIndex] = B[bIndex];
                    ++bIndex;
                    continue;
                }
 
                if (bIndex == B.Length)
                {
                    result[aIndex + bIndex] = A[aIndex];
                    ++aIndex;
                    continue;
                }
 
                if (A[aIndex] < B[bIndex])
                {
                    result[aIndex + bIndex] = A[aIndex];
                    ++aIndex;
                }
                else
                {
                    result[aIndex + bIndex] = B[bIndex];
                    ++bIndex;
                }
            }
            return result;
        }
 
        static void Main(string[] args)
        {
            //test data
            int[] A = { 8, -1, 3, 5, 0, -45, -6, 13, 55, 22 };
            Array.Sort(A);
            int[] B = { 5, -41, 3, 40, -45, -69, 13, -55, 522 };
            Array.Sort(B);
 
            //call
            int[] merged = merge(A, B);
        }

Автор публикации: