Сортировка — фундаментальная операция в информатике, и существуют различные алгоритмы для эффективного выполнения этой задачи. Одним из популярных алгоритмов сортировки является сортировка слиянием, известная своей простотой и превосходной временной сложностью в среднем и наихудшем случае. В этом посте мы рассмотрим различные методы реализации сортировки слиянием в Rust, а также приведем примеры кода.

Метод 1: рекурсивная сортировка слиянием
Рекурсивная реализация сортировки слиянием следует парадигме «разделяй и властвуй». Он предполагает деление массива на две половины, рекурсивную сортировку каждой половины и их обратное слияние. Вот пример кода:

fn merge_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }

    let mid = arr.len() / 2;
    let (left, right) = arr.split_at_mut(mid);

    merge_sort(left);
    merge_sort(right);

    merge(arr, left, right);
}
fn merge(arr: &mut [i32], left: &mut [i32], right: &mut [i32]) {
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i];
            i += 1;
        } else {
            arr[k] = right[j];
            j += 1;
        }
        k += 1;
    }

    while i < left.len() {
        arr[k] = left[i];
        i += 1;
        k += 1;
    }

    while j < right.len() {
        arr[k] = right[j];
        j += 1;
        k += 1;
    }
}

Метод 2: итеративная сортировка слиянием
Альтернативный подход к реализации сортировки слиянием заключается в использовании итеративного метода, использующего стратегию «снизу вверх». Этот метод позволяет избежать рекурсии и использует явный стек для управления подмассивами. Вот пример кода:

fn merge_sort(arr: &mut [i32]) {
    let len = arr.len();
    let mut width = 1;
    while width < len {
        let mut i = 0;
        while i < len {
            let mid = i + width;
            let end = mid + width;
            merge(arr, i, mid, end);
            i = end;
        }
        width *= 2;
    }
}
fn merge(arr: &mut [i32], left: usize, mid: usize, right: usize) {
    let mut i = left;
    let mut j = mid;
    let mut temp = Vec::with_capacity(right - left);
    while i < mid && j < right {
        if arr[i] <= arr[j] {
            temp.push(arr[i]);
            i += 1;
        } else {
            temp.push(arr[j]);
            j += 1;
        }
    }
    temp.extend_from_slice(&arr[i..mid]);
    temp.extend_from_slice(&arr[j..right]);
    arr[left..right].copy_from_slice(&temp[..]);
}

Сортировка слиянием – это мощный алгоритм сортировки с эффективной временной сложностью. В этой статье мы исследовали два метода реализации сортировки слиянием в Rust: рекурсивный подход и итеративный подход. Оба метода обеспечивают надежный способ эффективной сортировки массивов элементов. Поняв и внедрив эти алгоритмы, вы сможете оптимизировать производительность своего кода при решении задач сортировки в Rust.