UniLecs #181. Сортировка слиянием без использования дополнительной памяти

Задача: даны два отсортированных массива A и B размером m и n соот-но. Необходимо объединить элементы массива А с элементами массива B, поддерживая отсортированный порядок. То есть заполнить массив А первыми m наименьшими элементами и заполнить B оставшимися элементами.

Входные данные: A, B - массивы натуральных чисел, m, n - от 1 до 10^4.

Вывод: отсортированные согласно условию массивы A и B

Условие: преобразование должно быть сделано, используя только исходные два массива.

Пример:

A = [ 1, 4, 7, 9, 10 ]

B = [ 2, 3, 5, 8 ]

Answer:

A = [ 1, 2, 3, 4, 5 ]

B = [  7, 8, 9, 10 ]

Идея: мы рассматриваем каждый элемент массива А:

• Игнорируем элемент, если он уже находится в правильном порядке (т.е. элемент наименьший среди всех остальных элементов).
• В противном случае мы меняем его с наименьшим элементом, который оказывается первым элементом в массиве B. 
• После замены в B[0] находится новый элемент, поэтому проверяем не нарушен ли отсортированный порядок в массиве B. Если нарушен, ставим новый элемент в нужное место.

Детали смотрите в реализации.

Реализация:

https://gist.github.com/unilecs/7bd37816d1b1ea9b7fee9c4fcb3cd9a4

Play-test: https://dotnetfiddle.net/SBC0hP