ここでは高速に処理ができるアルゴリズムを紹介する。ここで高速と呼んでいるものは、O(nlogn)に分類できるものである。
13 43 45 56 <----- テープ1 7 18 68 95 <----- テープ2これらを、マージしよう。
13 43 45 56 < 7 18 68 95 13 43 45 56 7 < 18 68 95 43 45 56 7 13 < 18 68 95 43 45 56 7 13 18 < 68 95 45 56 7 13 18 43 < 68 95 56 7 13 18 43 45 < 68 95 7 13 18 43 45 56 < 68 95 7 13 18 43 45 56 68 95 <----- テープ3この場合、磁気テープを余分に1本必要とすることに注意。
上記基本原理を、1次元配列のデータに対して行なうために、データを2分割し、疑似的に2本の磁気テープを構成する。例を用いて、(内部的な)マージソートの動作を示そう。
入力データ n=2^3個とする。
45 56 43 13 95 18 7 68ステップ1
(45 56 43 13)と(95 18 7 68)の2組のデータに分ける。2組の各データをさらに分割する。
(45 56)と (43 13)と(95 18)と(7 68)上記操作を2つのデータの組になるまで、繰り返す。
ステップ2
2つのデータの各組に対し、マージ操作を行なう。よって、
(45 56) と (13 43) と (18 95) と (7 68)さらに、マージ操作を繰り返す。よって
(13 43 45 56) と (7 18 68 95)となる。さらに、マージ操作を行なう。 よって、
7 13 18 43 45 56 68 95となる。
1: void MergeSort( int data[], int left, int right ) { 2: int mid; 3: 4: if( left < right ) { 5: mid = (right - left + 1) / 2; 6: MergeSort( data, left, left+mid-1 ); 7: MergeSort( data, left+mid, right ); 8: Merge( data, left, left+mid ); 8: } 10: } 11: 12: void Merge( int data[], int l, int m ) { 13: int tmp[MaxNumber+1], h, i, j, k, r; 14: 15: i = l; 16: j = m; 17: r = 2*m-l; 18: k = l; 19: while( (i < m) && (j < r) ) { 20: if( data[i] < data[j] ) { 21: tmp[k] = data[i]; 22: i++; 23: } 24: else { 25: tmp[k] = data[j]; 26: j++; 27: } 28: k++; 29: } 30: if( i < m ) 31: for( h=i; h < m; h++ ) { 32: tmp[k] = data[h]; 33: k++; 34: } 35: if( j < r ) 36: for( h=j; h < r; h++ ) { 37: tmp[k] = data[h]; 38: k++; 39: } 40: for( h=l; h < r; h++ ) 41: data[h] = tmp[h]; 42: }マージソートの計算時間量は、n*log(n)である。データが2個になるまでデータの2分割を繰り返していく。この分割は、log(n)回行なわれる。各ステージでは、並べ替えが行なわれ、その計算量はO(n)である。よって、全体でn*log(n)となる。