ここでは高速に処理ができるアルゴリズムを紹介する。ここで高速と呼んでいるものは、Ｏ（ｎｌｏｇｎ）に分類できるものである。
13 43 45 56 <----- テープ１ 7 18 68 95 <----- テープ２これらを、マージしよう。
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 <----- テープ３この場合、磁気テープを余分に１本必要とすることに注意。
上記基本原理を、１次元配列のデータに対して行なうために、データを２分割し、疑似的に２本の磁気テープを構成する。例を用いて、（内部的な）マージソートの動作を示そう。
入力データ ｎ＝２＾３個とする。
45 56 43 13 95 18 7 68
ステップ１
(45 56 43 13)と(95 18 7 68)の２組のデータに分ける。２組の各データをさらに分割する。
(45 56)と (43 13)と(95 18)と(7 68)上記操作を２つのデータの組になるまで、繰り返す。
ステップ２
２つのデータの各組に対し、マージ操作を行なう。よって、
(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: }
マージソートの計算時間量は、ｎ＊ｌｏｇ（ｎ）である。データが２個になるまでデータの２分割を繰り返していく。この分割は、ｌｏｇ（ｎ）回行なわれる。各ステージでは、並べ替えが行なわれ、その計算量はＯ（ｎ）である。よって、全体でｎ＊ｌｏｇ（ｎ）となる。