Сортировка слиянием (Merge Sort)

Сортировка слиянием (Merge Sort) — это эффективный, стабильный алгоритм сортировки, использующий подход "разделяй и властвуй". Он работает следующим образом:

  1. Разделение: Массив делится на две половины, пока не останутся подмассивы размером 1 или 0.
  2. Слияние: Два отсортированных подмассива сливаются в один отсортированный массив.

Основные идеи сортировки слиянием

  1. Рекурсивное деление массива на половины: Если массив состоит из одного элемента или пуст, он уже отсортирован. В противном случае массив делится на две части, которые сортируются рекурсивно.
  2. Слияние отсортированных подмассивов: Два отсортированных подмассива сливаются в один, сохраняя порядок.
fun mergeSort(nums: IntArray, left: Int = 0, right: Int = nums.size - 1) {
    if (left < right) {
        val mid = left + (right - left) / 2

        // Рекурсивная сортировка левой и правой половин
        mergeSort(nums, left, mid)
        mergeSort(nums, mid + 1, right)

        // Слияние отсортированных половин
        merge(nums, left, mid, right)
    }
}

private fun merge(nums: IntArray, left: Int, mid: Int, right: Int) {
    val leftArray = nums.sliceArray(left..mid)
    val rightArray = nums.sliceArray(mid + 1..right)

    var i = 0 // Индекс для левой части
    var j = 0 // Индекс для правой части
    var k = left // Индекс для результирующего массива

    // Слияние двух временных массивов обратно в nums[left..right]
    while (i < leftArray.size && j < rightArray.size) {
        if (leftArray[i] <= rightArray[j]) {
            nums[k] = leftArray[i]
            i++
        } else {
            nums[k] = rightArray[j]
            j++
        }
        k++
    }

    // Копируем оставшиеся элементы левой части, если есть
    while (i < leftArray.size) {
        nums[k] = leftArray[i]
        i++
        k++
    }

    // Копируем оставшиеся элементы правой части, если есть
    while (j < rightArray.size) {
        nums[k] = rightArray[j]
        j++
        k++
    }
}

// Пример использования:
val nums = intArrayOf(4, 2, 7, 1, 9)
mergeSort(nums)
println(nums.joinToString(", ")) // Вывод: 1, 2, 4, 7, 9

Детальный разбор:

  1. Разделение массива:
    • В mergeSort массив делится на две части с помощью вычисления среднего индекса mid.
    • Рекурсивные вызовы mergeSort применяются к левому подмассиву nums[left..mid] и правому подмассиву nums[mid+1..right].
  2. Слияние отсортированных подмассивов:
    • Функция merge объединяет два отсортированных подмассива в один.
    • Создаются временные массивы leftArray и rightArray, содержащие элементы левой и правой частей исходного массива.
    • Переменные i, j, и k используются для отслеживания текущих индексов в левой части, правой части и объединенном массиве соответственно.
    • Два временных массива сливаются, сравнивая элементы один за другим и копируя меньший элемент обратно в исходный массив.
  3. Копирование оставшихся элементов:
    • После слияния основных частей, если остаются элементы в leftArray или rightArray, они копируются в исходный массив.

Преимущества и недостатки сортировки слиянием

Преимущества:

  • Гарантированная производительность: Время выполнения O(n log n) в худшем, среднем и лучшем случаях.
  • Стабильность: Сортировка слиянием является стабильной, что означает, что одинаковые элементы сохраняют свой относительный порядок.
  • Подходит для сортировки связных списков: В отличие от быстрой сортировки, сортировка слиянием хорошо работает с связными списками, так как не требует случайного доступа к элементам.

Недостатки:

  • Дополнительная память: Требует дополнительной памяти O(n) для временных массивов.
  • Сложность реализации: Более сложная для понимания и реализации по сравнению с простыми алгоритмами сортировки, такими как пузырьковая сортировка.

Оптимизации

  1. Iterative Merge Sort: Вместо рекурсивного подхода можно использовать итеративный подход, чтобы избежать проблем с переполнением стека для очень больших массивов.
fun mergeSortIterative(nums: IntArray) {
    val n = nums.size
    var currSize: Int
    var leftStart: Int

    // Сортируем подмассивы разного размера от 1 до n/2
    currSize = 1
    while (currSize <= n - 1) {
        leftStart = 0
        while (leftStart < n - 1) {
            val mid = minOf(leftStart + currSize - 1, n - 1)
            val rightEnd = minOf(leftStart + 2 * currSize - 1, n - 1)
            merge(nums, leftStart, mid, rightEnd)
            leftStart += 2 * currSize
        }
        currSize *= 2
    }
}