Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию merge и функцию merge_sort.

• Функция merge принимает два отсортированных массива, сливает их в один отсортированный массив и возвращает его. Если требуемая сигнатура имеет вид merge(array, left, mid, right), то первый массив задаётся полуинтервалом [left,mid) массива array, а второй – полуинтервалом [mid,right) массива array.
• Функция merge_sort принимает некоторый подмассив, который нужно отсортировать. Подмассив задаётся полуинтервалом — его началом и концом. Функция должна отсортировать передаваемый в неё подмассив, она ничего не возвращает.
• Функция merge_sort разбивает полуинтервал на две половинки и рекурсивно вызывает сортировку отдельно для каждой. Затем два отсортированных массива сливаются в один с помощью merge.

Заметьте, что в функции передаются именно полуинтервалы[begin,end), то есть правый конец не включается. Например, если вызвать merge_sort(arr, 0, 4), где arr=[4,5,3,0,1,2], то будут отсортированы только первые четыре элемента, изменённый массив будет выглядеть как arr=[0,3,4,5,1,2].

Реализуйте эти две функции.

Передаваемый в функции массив состоит из целых чисел, не превосходящих по модулю 10⁹ . Длина сортируемого диапазона не превосходит 10⁵.

При написании и отправке решений соблюдайте следующие правила:

• Отправляйте решение в виде файла. Если текст решения будет вставлен в форму, то будет возвращена ошибка.
• В качестве компилятора выберите Make.
• На Java назовите файл с решением Solution.java и реализуйте внутри класса указанные функции, для C# – Solution.cs
• Для остальных решений не используйте в качестве имени файла слово solution
• Укажите правильное разрешение для файла (.cpp, .java, .go. .js, .py). Для решений на C++ разрешение .h не поддерживается.

Go

package main 
func merge(arr []int, lf int, mid int, rg int) []int 
func merge_sort(arr []int, lf int, rg int)