Конкурентный Merge Sort

Решение

Анализ задачи

Требования:

• Реализовать Merge Sort с параллелизацией через горутины
• Использовать каналы для синхронизации
• Корректно объединять отсортированные части

Стратегия:

• Разделить массив пополам
• Сортировать каждую половину в отдельной горутине
• Объединить результаты

Решение

func concurrentMergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    // Базовый случай для малых массивов
    if len(arr) <= 16 {
        return simpleSort(arr)
    }
    
    // Делим массив пополам
    mid := len(arr) / 2
    
    // Каналы для результатов
    left := make(chan []int)
    right := make(chan []int)
    
    // Сортируем левую половину в горутине
    go func() {
        left <- concurrentMergeSort(arr[:mid])
    }()
    
    // Сортируем правую половину в горутине
    go func() {
        right <- concurrentMergeSort(arr[mid:])
    }()
    
    // Получаем отсортированные половины из каналов
    leftSorted := <-left
    rightSorted := <-right
    
    // Объединяем два отсортированных массива
    return merge(leftSorted, rightSorted)
}

// Простая сортировка для малых массивов
func simpleSort(arr []int) []int {
    for i := 0; i < len(arr)-1; i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i] > arr[j] {
                arr[i], arr[j] = arr[j], arr[i]
            }
        }
    }
    return arr
}

// Объединение двух отсортированных массивов
func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    
    // Добавляем оставшиеся элементы
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    
    return result
}

Пояснения реализации

1. Базовый случай

• Массивы из одного элемента уже отсортированы
• Для малых массивов (≤16 элементов) используем простую сортировку, чтобы не создавать горутины

2. Разделение

• Делим массив ровно пополам в точке mid
• Левая часть: arr[:mid], правая: arr[mid:]

3. Параллельная сортировка

• Каждую половину сортируем в отдельной горутине
• Результаты отправляются в каналы left и right
• Главная горутина ждёт результатов через <-left и <-right

4. Объединение (merge)

• Два указателя i и j идут по обоим массивам
• На каждом шаге берём меньший элемент
• После цикла добавляем оставшиеся элементы

Пример выполнения

Входящий массив: [38, 27, 43, 3, 9, 82, 10]

Уровень 1:
  Левая горутина:  [38, 27, 43, 3]
  Правая горутина: [9, 82, 10]

Уровень 2:
  [38, 27] и [43, 3] — сортируются параллельно
  [9] и [82, 10] — сортируются параллельно

Уровень 3:
  [27, 38] + [3, 43] = [3, 27, 38, 43]
  [9] + [10, 82] = [9, 10, 82]

Итоговое слияние:
  [3, 27, 38, 43] + [9, 10, 82] = [3, 9, 10, 27, 38, 43, 82]

Полный пример с тестированием

package main

import (
    "fmt"
    "sort"
)

func concurrentMergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    if len(arr) <= 16 {
        return simpleSort(arr)
    }
    
    mid := len(arr) / 2
    
    left := make(chan []int)
    right := make(chan []int)
    
    go func() {
        left <- concurrentMergeSort(arr[:mid])
    }()
    
    go func() {
        right <- concurrentMergeSort(arr[mid:])
    }()
    
    leftSorted := <-left
    rightSorted := <-right
    
    return merge(leftSorted, rightSorted)
}

func simpleSort(arr []int) []int {
    for i := 0; i < len(arr)-1; i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i] > arr[j] {
                arr[i], arr[j] = arr[j], arr[i]
            }
        }
    }
    return arr
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    
    return result
}

func main() {
    arr := []int{38, 27, 43, 3, 9, 82, 10}
    sorted := concurrentMergeSort(arr)
    fmt.Println("Sorted:", sorted) // [3, 9, 10, 27, 38, 43, 82]
    
    // Проверка
    expected := []int{3, 9, 10, 27, 38, 43, 82}
    fmt.Println("Correct:", sort.IntsAreSorted(sorted))
}

Сложность

• Временная сложность: O(n log n) в среднем и худшем случаях
• Пространственная сложность: O(n) для временных массивов + O(log n) для стека рекурсии
• Параллелизм: использует 2^(log n) = n горутин на максимальной глубине рекурсии

Оптимизация

Настройка порога 16 может зависеть от размера массива:

• Для очень больших массивов увеличить порог (например, 1024)
• Для малых увеличить параллелизм