Реализация Merge Sort
Другим промежуточным алгоритмом сортировки, который очень распространен, является сортировка слияния. Подобно быстрой сортировке, сортировка слиянием также использует метод рекурсивного анализа для разделения массива. Сортировка использует тот факт, что легче сортировать два массива меньшего размера, нежели один большего.
В качестве входных данных начнем с неотсортированного массива. Как мы можем перейти к двум отсортированным массивам? Мы можем рекурсивно разделить исходный ввод на два, пока не достигнем базового случая массива с одним элементом. Массив из одного элемента естественно сортируется, поэтому мы можем начать комбинировать. Эта комбинация будет раскручивать рекурсивные вызовы, разделяющие исходный массив, в конечном итоге создавая окончательный отсортированный массив всех элементов.
Затем выполняются шаги сортировки слияния:
1) Рекурсивно разделить входной массив пополам, пока не будет создан массив только с одним элементом.
2) Объединтить каждый отсортированный подмассив вместе, чтобы получить окончательный отсортированный массив.
Сортировка Merge - это эффективный метод сортировки со алгоритмически-оптимальной сложностью O (nlog (n)) . Этот алгоритм популярен, потому что он прост в реализации.
Это будет последний эффективный алгоритм сортировки, который мы рассмотрим здесь. Однако позже в разделе о структурах древовидных данных мы опишем сортировку кучи (HeapSort), еще один эффективный метод сортировки, который требует реализацию бинарной кучи.
Инструкции: Напишите функцию mergeSort которая принимает массив целых чисел в качестве входных данных и возвращает массив этих целых чисел в отсортированном порядке от наименьшего к наибольшему. Хороший способ реализовать это - написать одну функцию, например merge , которая отвечает за объединение двух отсортированных массивов и другую функцию, например, mergeSort , которая отвечает за слияние. Удачи!
Заметка:
Мы вызываем эту функцию из-за кулис; тестовый массив, который мы используем, закомментирован в редакторе. Попробуйте logging array чтобы увидеть ваш алгоритм сортировки в действии!