Какова основная идея и преимущества алгоритма сортировки слиянием?

Алгоритм сортировки слиянием (Merge Sort) основан на принципе «разделяй и властвуй». Он рекурсивно делит исходный массив на две половины, сортирует каждую из них, а затем сливает две отсортированные части в один отсортированный массив.

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

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

Пример на Java:

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    // Логика слияния двух отсортированных подмассивов
}