Sort multiple arrays at once (tools/multisort.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-07-13 17:32:24+09:00
• Include: #include "tools/multisort.hpp"

(1)
template <std::ranges::random_access_range R1, std::ranges::random_access_range R2, typename Comp>
requires std::sortable<std::vector<int>::iterator, Comp>
void multisort(R1&& a, R2&& b, Comp comp);

(2)
template <std::ranges::random_access_range R1, std::ranges::random_access_range R2, std::ranges::random_access_range R3, typename Comp>
requires std::sortable<std::vector<int>::iterator, Comp>
void multisort(R1&& a, R2&& b, R3&& c, Comp comp);

(3)
template <std::ranges::random_access_range R1, std::ranges::random_access_range R2, std::ranges::random_access_range R3, std::ranges::random_access_range R4, typename Comp>
requires std::sortable<std::vector<int>::iterator, Comp>
void multisort(R1&& a, R2&& b, R3&& c, R4&& d, Comp comp);

(4)
template <std::ranges::random_access_range R1, std::ranges::random_access_range R2, std::ranges::random_access_range R3, std::ranges::random_access_range R4, std::ranges::random_access_range R5, typename Comp>
requires std::sortable<std::vector<int>::iterator, Comp>
void multisort(R1&& a, R2&& b, R3&& c, R4&& d, R5&& e, Comp comp);

It sorts multiple arrays at once by the same criteria. Strictly speaking, it calculates $p$, the permutation of $(0, 1, \ldots, n - 1)$ such that $p_0 \leq p_1 \leq \cdots \leq p_{n - 1}$ where $x \leq y$ is defined by !comp(y, x), and runs the following operations at once.

\[\begin{align*} \left\{\begin{array}{ll} a_0 & \leftarrow a_{p_0}\\ a_1 & \leftarrow a_{p_1}\\ \vdots &\\ a_{n - 1} & \leftarrow a_{p_{n - 1}}\\ b_0 & \leftarrow b_{p_0}\\ b_1 & \leftarrow b_{p_1}\\ \vdots &\\ b_{n - 1} & \leftarrow b_{p_{n - 1}}\\ \vdots & \end{array}\right.& \end{align*}\]

Constraints

• (1)
  • $|a| = |b|$
• (2)
  • $|a| = |b| = |c|$
• (3)
  • $|a| = |b| = |c| = |d|$
• (4)
  • $|a| = |b| = |c| = |d| = |e|$

Time Complexity

• $O(n \log n)$

License

• CC0

Author

• anqooqie

Verified with

• tests/multisort.test.cpp

Code

#ifndef TOOLS_MULTISORT_HPP
#define TOOLS_MULTISORT_HPP

#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <ranges>
#include <utility>
#include <vector>

namespace tools {
  namespace detail {
    namespace multisort {
      template <::std::ranges::random_access_range R>
      void sort(R&& r, const ::std::vector<int>& p) {
        ::std::vector<::std::ranges::range_value_t<R>> sorted_r(p.size());
        for (int i = 0; i < ::std::ssize(p); ++i) {
          sorted_r[i] = ::std::move(::std::ranges::begin(r)[p[i]]);
        }
        ::std::ranges::move(sorted_r, ::std::ranges::begin(r));
      }
    }
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    ::std::ranges::random_access_range R4,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, R4&& r4, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);
    assert(::std::ranges::ssize(r4) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
    ::tools::detail::multisort::sort(::std::forward<R4>(r4), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    ::std::ranges::random_access_range R4,
    ::std::ranges::random_access_range R5,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, R4&& r4, R5&& r5, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);
    assert(::std::ranges::ssize(r4) == n);
    assert(::std::ranges::ssize(r5) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
    ::tools::detail::multisort::sort(::std::forward<R4>(r4), p);
    ::tools::detail::multisort::sort(::std::forward<R5>(r5), p);
  }
}

#endif

#line 1 "tools/multisort.hpp"



#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <ranges>
#include <utility>
#include <vector>

namespace tools {
  namespace detail {
    namespace multisort {
      template <::std::ranges::random_access_range R>
      void sort(R&& r, const ::std::vector<int>& p) {
        ::std::vector<::std::ranges::range_value_t<R>> sorted_r(p.size());
        for (int i = 0; i < ::std::ssize(p); ++i) {
          sorted_r[i] = ::std::move(::std::ranges::begin(r)[p[i]]);
        }
        ::std::ranges::move(sorted_r, ::std::ranges::begin(r));
      }
    }
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    ::std::ranges::random_access_range R4,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, R4&& r4, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);
    assert(::std::ranges::ssize(r4) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
    ::tools::detail::multisort::sort(::std::forward<R4>(r4), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    ::std::ranges::random_access_range R4,
    ::std::ranges::random_access_range R5,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, R4&& r4, R5&& r5, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);
    assert(::std::ranges::ssize(r4) == n);
    assert(::std::ranges::ssize(r5) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
    ::tools::detail::multisort::sort(::std::forward<R4>(r4), p);
    ::tools::detail::multisort::sort(::std::forward<R5>(r5), p);
  }
}

Back to top page