マージソート

マージソートを書いてみてください，というのは私が面接官をするときに必ず聞いている質問の一つ．というわけでマージソートである．

最初からソートした２つの配列を１つにする答えをもらえれば，及第点ではあるが，以下のようにソートされていない１つの配列を文字通りソートするアルゴリズムの答えであれば，満点である
．

#include <iostream>
#include <array>
#include <cmath>
using namespace std;

#define ARRAY_SIZE 8

void init(array<int,ARRAY_SIZE>& a) {

 a[0] = 10; a[1] = 5; a[2] = 3; a[3] = 6;
 a[4] = 6; a[5] = 9; a[6] = 15; a[7] = 1;
}

void dump(array<int,ARRAY_SIZE>& a) {

 for( int i =0;i < a.size();i++ )
  cout << a.at(i) << ' ';
 cout << endl;
 
}

void mergesort(array<int,ARRAY_SIZE>& arr) {
 
 int divider = 2;
 int compartment;
 int t;
 while( divider <= ARRAY_SIZE ) {
  compartment = ARRAY_SIZE / divider;
  for( int i = 0;i < compartment;i++ ) {
   for( int j = i * divider;j < divider;j++ ) {
    for( int k = j + 1;k < divider;k++ ) {
     if( arr[j] > arr[k] ) {
      t = arr[j];
      arr[j] = arr[k];
      arr[k] = t;
     }
    }
   }
  }
  divider *= 2;
 }
}

int main() {
 array<int,ARRAY_SIZE> arr;
 init(arr);
 dump(arr);

 mergesort(arr);
 dump(arr);
}

実行結果は以下の通り

10 5 3 6 6 9 15 1
1 3 5 6 6 9 10 15