ソートアルゴリズムの勉強2

ソートアルゴリズムの勉強 - yebis0942’s blogの続き。

マージソートのマージする部分で、「配列Aと配列Bのどちらも空ではないなら」という条件文にするべきところを「配列Aと配列Bのどちらかが空ではないなら」と書いていたのが原因だった。コードを慣れないC++で書いているので、自分の言語に対する知識が間違っているのか、ロジックの理解に問題があるのかはっきりしなくて難しい。しかし自分がそれなりに習熟しているのはスクリプト言語ばかりで、それでソートとかを書いてもアルゴリズムの勉強をしているという気分が出ない。

vector<int> mergesort(vector<int> v) {
  if (v.size() == 1) return v;

  if (v.size() == 2) {
    if (v[0] > v[1]) swap(v[0], v[1]);
    return v;
  }

  vector<int> a, b;
  for (int i = 0; i < v.size(); i++) {
    if (i <= v.size() / 2)
      a.push_back(v[i]);
    else
      b.push_back(v[i]);
  }

  auto a_sorted = mergesort(a);
  auto b_sorted = mergesort(b);
  int a_sorted_idx = 0;
  int b_sorted_idx = 0;
  vector<int> sorted;

  while (a_sorted_idx < a_sorted.size() && b_sorted_idx < b_sorted.size()) { // ここを || にしていた。
    if (a_sorted[a_sorted_idx] > b_sorted[b_sorted_idx]) {
      sorted.push_back(b_sorted[b_sorted_idx++]);
    } else {
      sorted.push_back(a_sorted[a_sorted_idx++]);
    }
  }

  while (a_sorted_idx < a.size())
    sorted.push_back(a_sorted[a_sorted_idx++]);

  while (b_sorted_idx < b.size())
    sorted.push_back(b_sorted[b_sorted_idx++]);

  return sorted;
}