内部整列どのデータにも均等な時間でアクセスできる。できるだけ高速に整列したい。(理想的なRAMモデル上のアルゴリズムではこっち)外部整列CPU-メモリ間のデータ転送速度より、ディスク-メモリ間のデータ転送速度が極端に遅い。全体の整列をできるだけ高速にしたい。(ディスクーメモリ間のデータ転送をあまり行わないようにする。配列に入力データがあるとして説明します。隣同士比べて、小さいほうを上(添字の小さい方)に順にもっていく。先頭の方は、ソートされている状態にしておく。これらを繰り返して、全体をソートする。91313バブルソートの実現1/*交換用の関数A[i]とA[j]を交換する。先頭から順に、その位置に入るデータを決める。(最小値を求める方法で選択する。)その位置のデータと選択されたデータを交換する。これらを繰り返して、全体をソートする。実際は2重ループにするほうが速いと思われる。(でも、オーダーでは、同じ。先頭の方は、ソート済みの状態にしておく。未ソートのデータを、ソート済みの列に挿入し、ソート済みの列を1つ長くする。これらを繰り返して、全体をソートする。181813544438445858445812未ソート45413131313131395869999991397222222213挿入ソートの実現1(挿入位置を求める)/*挿入位置を見つける関数、A[0]からA[i-1]までソート済みのとき、A[i]の順番を求める。アルゴリズム(挿入ソートを元に高速化した、シェルソートっていうものもあるが省略。)ヒープソート方針ヒープを使ってソートする。先頭から順にヒープに挿入し、データ全体をヒープ化する。最大値を取り出して、最後のデータにする。問題を小分けにして、あとで組み合わせる。(分割統治法)小分けした問題は、再帰的にソートする。大きいソートの列をつくる。12分割もし2つのソート列があったら、マージ操作によって、長いソート列がえられることがわかった。問題のサイズが小さくなっていることに注意する。列を二等分にして、再帰的にソートする。5A[0]からA[3]までソートして。2A[4]からA[7]までソートして。配列Bと配列Cを配列Aにマージする。カウンタ*/while(iA<=numB+numC-1){if(B[iB]<C[iC]){A[posA+iA]=B[iB];iB++;}else{A[posA+iA]=C[iC];iC++}iA++;}return;}マージソートの実現/*概略です。/*作業用の配列*/if(left==right)return;mid=(left+right)/2;marge_sort(left,mid,A);marge_sort(mid,right,A);/*ここに、A[left]からA[mid]を配列Bに、A[mid]からA[right]を配列Cにコピーする処理を書く。