マージソート
(C++/other/merge_sort.hpp)

• View this file on GitHub
• Last update: 2024-03-16 14:18:14+09:00
• Include: #include "C++/other/merge_sort.hpp"

verified: 027 - Sorting

Code

#pragma once

#include <vector>
#include <limits>
template <class T> inline void merge(std::vector<T>& v, const int left, const int mid, const int right) {
    const int n1 = mid - left, n2 = right - mid;
    std::vector<T> l(n1 + 1), r(n2 + 1);
    for(int i = 0; i < n1; ++i) {
        l[i] = v[left + i];
    }
    for(int i = 0; i < n2; ++i) {
        r[i] = v[mid + i];
    }
    l[n1] = r[n2] = std::numeric_limits<T>::max();
    int i = 0, j = 0;
    for(int k = left; k < right; ++k) {
        if(l[i] <= r[j]) {
            v[k] = l[i++];
        } else {
            v[k] = r[j++];
        }
    }
}
template <class T> inline void merge_sort(std::vector<T> &v, const int l, const int r) {
    if(l + 1 < r) {
        const int mid = (l + r) / 2;
        merge_sort(v, l, mid);
        merge_sort(v, mid, r);
        merge(v, l, mid, r);
    }
}

/**
 * @brief マージソート
 * @docs docs/merge_sort.md
 */

#line 2 "C++/other/merge_sort.hpp"

#include <vector>
#include <limits>
template <class T> inline void merge(std::vector<T>& v, const int left, const int mid, const int right) {
    const int n1 = mid - left, n2 = right - mid;
    std::vector<T> l(n1 + 1), r(n2 + 1);
    for(int i = 0; i < n1; ++i) {
        l[i] = v[left + i];
    }
    for(int i = 0; i < n2; ++i) {
        r[i] = v[mid + i];
    }
    l[n1] = r[n2] = std::numeric_limits<T>::max();
    int i = 0, j = 0;
    for(int k = left; k < right; ++k) {
        if(l[i] <= r[j]) {
            v[k] = l[i++];
        } else {
            v[k] = r[j++];
        }
    }
}
template <class T> inline void merge_sort(std::vector<T> &v, const int l, const int r) {
    if(l + 1 < r) {
        const int mid = (l + r) / 2;
        merge_sort(v, l, mid);
        merge_sort(v, mid, r);
        merge(v, l, mid, r);
    }
}

/**
 * @brief マージソート
 * @docs docs/merge_sort.md
 */

Back to top page