Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию 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].
Реализуйте эти две функции.
Передаваемый в функции массив состоит из целых чисел, не превосходящих по модулю 109 . Длина сортируемого диапазона не превосходит 105.
При написании и отправке решений соблюдайте следующие правила:
- Отправляйте решение в виде файла. Если текст решения будет вставлен в форму, то будет возвращена ошибка.
- В качестве компилятора выберите 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)