Сортировка слиянием.

Сортировка слиянием использует подход «разделяй и властвуй». Это значит, что он делит проблему (массив) на более мелкие части, решает каждую часть отдельно, а затем объединяет (сливает) решения для получения окончательного результат.

Сортировка слиянием имеет среднюю и худшую асимптотическую сложность O(n log n), где n - размер массива. Это делает ее одной из самых эффективных алгоритмов сортировки для больших массивов. Кроме того, сортировка слиянием является стабильной, т.е. она сохраняет относительный порядок равных элементов в исходном массиве.

Разделяй

Разделение массива пополам: Сначала массив делится на две примерно равные части. Этот процесс продолжается рекурсивно для каждой половины, пока массивы не станут размером 1 или 0 (такие массивы считаются уже отсортированными).

Например, массив [38, 27, 43, 3, 9, 82, 10] делится на: [38, 27, 43] и [3, 9, 82, 10]

Рекурсивное деление: Каждая из этих частей снова делится на две части:

[38, 27, 43] делится на [38] и [27, 43] [27, 43] делится на [27] и [43] [3, 9, 82, 10] делится на [3, 9] и [82, 10] [3, 9] делится на [3] и [9] [82, 10] делится на [82] и [10]

Остановка деления: Когда массивы состоят из одного элемента, деление прекращается. Таким образом, мы получаем несколько массивов размером 1.

Властвуй

Слияние отсортированных массивов: Теперь начинается процесс слияния. Два отсортированных массива объединяются в один отсортированный массив.

Например: [38] и [27] сливаются в [27, 38] [27, 38] и [43] сливаются в [27, 38, 43] [3] и [9] сливаются в [3, 9] [82] и [10] сливаются в [10, 82] [3, 9] и [10, 82] сливаются в [3, 9, 10, 82]

Продолжение слияния: Продолжается слияние до тех пор, пока не будет получен один отсортированный массив:

[27, 38, 43] и [3, 9, 10, 82] сливаются в [3, 9, 10, 27, 38, 43, 82]

Алгоритм

Сортировка слиянием состоит из следующих шагов:

1. Если размер массива равен 1, то он уже отсортирован, и мы возвращаем его.
2. Разбиваем массив на два подмассива примерно одинакового размера.
3. Рекурсивно применяем сортировку слиянием к каждому из подмассивов.
4. Объединяем два отсортированных подмассива в один отсортированный массив, используя алгоритм слияния.

Алгоритм слияния работает следующим образом:

1. Создаем новый массив для хранения отсортированного результата.
2. Проходим по двум отсортированным подмассивам, сравнивая их элементы и добавляя меньший элемент в новый массив.
3. Когда один из подмассивов закончится, добавляем все оставшиеся элементы другого подмассива в новый массив.

Работает на двух указателях

def mergeSort(arr):  
    if len(arr) > 1:  
        mid = len(arr) // 2  
        leftArr = arr[:mid]  
        rightArr = arr[mid:]  
        mergeSort(leftArr)  
        mergeSort(rightArr)  
		
        i = j = k = 0  
		
        while i < len(leftArr) and j < len(rightArr):  
            if leftArr[i] < rightArr[j]:  
                arr[k] = leftArr[i]  
                i += 1  
            else:  
                arr[k] = rightArr[j]  
                j += 1  
            k += 1  
		
        while i < len(leftArr):  
            arr[k] = leftArr[i]  
            i += 1  
            k += 1  
		
        while j < len(rightArr):  
            arr[k] = rightArr[j]  
            j += 1  
            k += 1