JPH08221254A - マージソート方法及びマージソート装置 - Google Patents

Abstract

(57)【要約】 【目的】 マージソート方法に関し、ソート処理の高速
化を目的とする。 【構成】 ソート対象のデータ列を検索してソート処理
不要な部分集合を抽出し、この部分集合をソート済み並
びとして併合する所定のマージ処理を行って、該データ
列をソートする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はマージソート方法および
マージソート装置の改良に関する。データベースを作成
する場合にデータを昇順または降順に並べるとか、その
データベースに新たなデータが追加された場合に並べ替
えの必要性が生じた場合などにおいて、データのソート
（整列）処理が実施される。

【０００２】そのソート方法の１つとして、データ列の
各データを交互に振り分けた後、それぞれソートしつつ
併合（マージ）していくマージソート方法が広く採用さ
れているが、データ量が多いとソート処理に時間がかか
る。

【０００３】近年では、端末装置においても、業務処理
上のデータ検索時間の短縮が要望されているため、ソー
ト処理頻度が増加しつつあり、ソート処理の高速化が要
望されている。

【０００４】

【従来の技術】図８は従来例のマージソート方法説明図
である。図８は、マージソート方法の１例を示したもの
で、例えば、レコードＮＯが０〜７までの８データをデ
ータの大きさの順（昇順）に並べ替える場合、先ず、レ
コードＮＯ＝０のデータとレコードＮＯ＝１のデータを
振り分けた後、併合（マージ）する。この併合の際、デ
ータの大きさの順に並べる。この結果図のに示すデー
タ列が得られる。

【０００５】続いて、レコードＮＯ＝２のデータとレコ
ードＮＯ＝３のデータを振り分けた後マージすると、
のデータ列が得られる。このようにして、それぞれ２組
のデータがソートされたデータ列，，，が得ら
れる。

【０００６】次のステップでデータ列とデータ列と
をマージすると、データ列が得られ、同様にしてデー
タ列，からデータ列が得られ、このデータ列と
とをマージすると１つのデータ列が得られる。この
データ列が、目的とする昇順にソートされたデータ列
となる。

【０００７】なお、マージする場合の処理は、例えばデ
ータ列とデータ列とを例にとると次の通りである。
先ず、データ列の先頭（０００２）とデータ列の先
頭（０００１）とを比較する。（０００１）の方が小さ
いから、このデータをバッファに格納する。次にデータ
列の（０００２）とデータ列の（０００６）とを比
較する。（０００２）の方が小さいから、（０００２）
をバッファ内の（０００１）の次に格納する。次はデー
タ列の（０００５）とデータ列の（０００６）と比
較する。（０００５）の方が小さいから、（０００５）
をバッファの（０００２）の次に格納する。ここで残り
の比較データがないから、（０００６）を最後に格納す
る。

【０００８】このように、２組のデータ列を整列済みの
並びごとに併合する手続きを繰り返すことにより、昇順
に整列された１つのデータ列が得られる。

【０００９】

【発明が解決しようとする課題】端末装置における業務
処理等でデータベースが検索される場合が多いが、デー
タベースが昇順または降順のごとく、ある決められた順
にソートされていないと検索に時間がかかる。このた
め、データの追加などによってソートされていないデー
タが一定量に達すると、通常自動的にソート処理が実施
されるようになっており、その間オペレータは待たされ
る。

【００１０】このソート処理には前述したマージソート
法等が採用されているが、近年ではハードディスクの容
量の増大によってデータ量が多くなっており、益々ソー
ト処理に時間を要している。

【００１１】本発明は、上記課題に鑑み、ソート時間を
短縮するマージソート方法を提供することを目的とす
る。

【００１２】

【課題を解決するための手段】上記課題を解決するた
め、本発明のマージソート方法は、図１本発明の原理図
に示すように、 (1) ソート対象のデータ列を検索してソート処理不要な
部分集合を抽出し、この部分集合をソート済み並びとし
て併合する所定のマージ処理を行って、該データ列をソ
ートする。 (2) 上記(1) を実現するマージソート処理装置として、
ソート処理対象のデータ列を検索してソート不要な部分
集合を抽出するソート不要部抽出処理部と、前記部分集
合を基準として所定のマージ処理を行うマージ処理部と
を備えるように構成する。

【００１３】

【作用】

(1) 先ず、ソート対象のデータ列からソート処理不要な
一連のデータ列を部分集合（ソート不要部）として抽出
する。この部分集合を最初の整列済み並びとして、振り
分け、且つ併合する所定のマージ処理を遂行していく。

【００１４】一般にソートする場合には、整列済みのデ
ータ列の部分が多いから、この集合をスタートとしてマ
ージソートを遂行すると、大幅にソート時間が短縮され
る。なお、この際、各部分集合の大きさは一定である必
要はない。 (2) 上記(1) を実現する装置において、ソート不要部抽
出処理部はソート対象のデータ列からソート処理不要な
一連のデータを部分集合として抽出し、マージ処理部
は、この部分集合を基準として所定のマージ処理を行
う。

【００１５】以上のごとく、ソート不要な部分集合が大
きければ、従来例と比較して、最初の数段階のマージ処
理を省くことができ、ソート処理速度を大幅に短縮する
ことができる。

【００１６】

【実施例】図２は一実施例の構成図、図３は基本動作フ
ローチャート図、図４はソート不要部分抽出処理フロー
チャート図、図５はソート不要部分抽出処理例を表す
図、図６はマージソート処理フローチャート図、図７は
マージソート処理例を表す図である。

【００１７】本実施例では、具体的説明として、図８に
示す８レコード（レコードはデータの単位）のデータ列
に適用したものを示す。このレコード数はソート処理を
行うバッファ容量に制限されるもので、この部分の処理
はいわゆる内部ソートと称される。ソート対象のデータ
列がこのバッファ容量（ここでは８レコード）より大き
い場合、この８レコードをブロックとして、いわゆる外
部ソートを行う。

【００１８】図２は、データ処理装置（端末装置）のう
ちのマージソート部分を示したものである。図２におい
て、１は中央処理ユニットＣＰＵで、プログラムで構成
される下記各部を走行させ、本実施例のマージソート処
理の制御を行う。

【００１９】２はマージソート制御部で、データ読込処
理部３，ソート不要部抽出処理部４，ソート不要部マー
ジ処理部５，データ書込処理部６より構成される。ここ
で、データ読込処理部３は、ファイル装置７よりソート
対象のデータ列のうちからバッファ容量に応じた数のデ
ータを順に読み出してバッファ９に格納するもの、ソー
ト不要部抽出処理部４は、バッファ９に格納されたデー
タをサーチし、ソート処理不要（ここでは昇順とする）
な連続したデータ列（ソート不要部）を抽出し、そのデ
ータ列の先頭レコードＮＯをソートインデックス10に保
存するもの、ソート不要部マージ処理部５は、ソートイ
ンデックス10を参照し、ソート不要部間のマージソート
処理を行うもの、データ書込処理部６は、ソート完了し
たレコードＮＯにデータを置換してファイル装置７に格
納するものである。

【００２０】７はファイル装置で、ソート対象データが
格納されている。８はメモリで、マージソート処理を行
うためのバッファ９と、マージ処理を行うための後述す
るソートインデックス10などが含まれる。

【００２１】ここで、ソートインデックス10はソート不
要部の先頭レコードＮＯがレコードＮＯ順に格納された
もので、後述するが、図５にその生成過程を示してい
る。以下、次のようにしてマージソート処理が行われ
る。

【００２２】〔基本動作〕図３参照 (1) ファイル装置７より読込まれたデータ列はソート不
要部抽出処理部４によってサーチされ、ソート不要部抽
出処理が行われる。この結果、ソート不要部の先頭レコ
ードＮＯのみを格納したソートインデックス10と、各ソ
ート不要部のレコードＮＯ数が得られる。 (2) ソート不要部マージ処理部５によって各ソート不要
部間のマージ処理が行われる。この際レコードＮＯのみ
がソートされる。 (3) マージ処理が完了すると、ソートされたレコードＮ
Ｏが実データに置き換えられ、ファイル装置７に格納さ
れる。

【００２３】以下、詳細な動作は以下の通りである。 〔ソート不要部抽出処理〕図４参照 前述した基本動作(1) に相当し、マージ処理の前処理と
して行われる。 (1) データ読込処理部３は、読み込み可能なレコード数
分（ｎ) のデータをバッファ９に読み込む。 (2) ソートインデックス10の初期化を行う。ここで、バ
ッファ９に格納されたデータに対し、レコードＮＯとし
て０から７までを付与する。 (3) 先頭から順に隣り合うレコードを比較する。先ず、
ｍ＝０として（ｍ）と（ｍ＋１）を比較する。ここで
（ｍ）はレコードＮＯ＝ｍの内容を表す。 (4) （ｍ）＞（ｍ＋１）ならば、（ｍ＋１）のレコード
ＮＯをソートインデックス10に保存する。この保存され
たレコードＮＯがソート不要部の先頭レコードとなる。
（ｍ）≦（ｍ＋１）ならば、下記(6) に進む。 (5) ソートインデックス10に格納したレコードＮＯ数を
計数する。 (6) ｍ＝ｍ＋１として、(3) から繰り返す。

【００２４】以上により、図５に示すようなソートイン
デックス10が得られる。即ち、初期値としてｍ１＝０
が保存され、次にレコードＮＯ＝２のデータとレコード
ＮＯ＝３のデータとの比較でレコードＮＯ＝２までが
ソート不要部と判明するので、ｍ１＋１＝ｍ２＝３が保
存され、レコードＮＯ＝５のところで同様にソート要
となるのでｍ３＝５が保存される。そして、それぞれレ
コードＮＯ数として、３（Ａ群），２（Ｂ群），３（Ｃ
群）が計数される。

【００２５】〔マージソート処理〕ソート不要部マージ
処理部５の処理で、前述した基本動作(1) のソート不要
部間のマージである。この際、ソートインデックス10と
前述したレコードＮＯ数が使用される。ソートインデッ
クス10はマージ処理されるごとに併合され、最後はソー
トインデックス数は1 となる。

【００２６】図３に示すように、先ず、ソートインデッ
クス数を検索する。本例では、図５に示すように、最初
はｍ１，ｍ２，ｍ３まであるからソートインデックス数
は３であるからマージ処理を行う。１ならばすべて整列
したことを表すからマージ処理を終了する。

【００２７】ソートインデックス数＞１ならば、ソート
インデックス10の先頭から２組づつデータ群を取り出し
て（図１ではＡとＢ，ＣとＤ、図５ではＡとＢ，Ｃ）、
それぞれマージ処理を行う。

【００２８】以下１組（Ａ群，Ｂ群）についてマージ処
理例を説明する。図６，図７参照 (1) ソートインデックス10を参照して、２つのデータ群
Ａ，Ｂの先頭からレコードＮＯを１つづつ取り出す。 (2) そのレコードＮＯに対応する実データ（Ａ），
（Ｂ）をバッファ９より抽出する。 (3) 抽出した実データを比較し、（Ａ）≧（Ｂ）なら
ば、（Ｂ）をバッファ９に設けた出力バッファに格納す
る。 (4) 一方、（Ａ）＜（Ｂ）ならば、（Ａ）を出力バッフ
ァに格納し、次にその（Ｂ）と次の（Ａ）とを比較す
る。

【００２９】上記(3) と(4) とが繰り返され、比較する
データが無くなると、残った側のデータを出力バッファ
に順に格納して終了する。この結果、Ａ群とＢ群のレコ
ードＮＯが併合され、ソートインデックス10が更新され
る。この更新により、Ａ，Ｂが併合されたソートインデ
ックス10が生成される。同時に対応するレコードＮＯ数
も更新される。

【００３０】以上により、先頭２組づつマージ処理を行
い、次にマージされたデータ２組づつのマージ処理を行
う。この結果、出力バッファには、最終的にソートされ
たレコードＮＯが得られるので、実データに置き換えら
れて、ファイル装置７に格納される。

【００３１】図７で以上のことを説明すると次のように
なる。最初はＡ群とＢ群の比較であり、ステップ１の
の比較が行われる。このため、先ず、ソートインデック
ス10を参照して、Ａ群，Ｂ群の先頭レコードＮＯとし
て、レコードＮＯ＝０，レコードＮＯ＝３を取り出す。
（Ａ）＝０００２，（Ｂ）＝０００１であるから、
（Ａ）≧（Ｂ）となって、（Ｂ）のレコードＮＯ＝３を
出力バッファに格納する。

【００３２】続いてステップ１のの比較を行う。
（Ｂ）としてＢ群のうちから次のレコードＮＯのデータ
（０００７）を抽出し、（Ａ）＝（０００２）と比較す
る。この結果（Ａ）のレコードＮＯ＝０が出力バッファ
に格納される。

【００３３】このようにして、比較，が行われ、最
後に（０００７）が残るから、このレコードＮＯを出力
バッファに格納する。そしてソートインデックス10の数
は２となり、図７に示した構成となる。

【００３４】このＡ群とＢ群のマージが終了すると、ス
テップ２として、（Ａ＋Ｂ）とＣとのマージ処理が前述
と同様に行われる。そしてソートインデックス10の数は
１となるからマージが終了する。

【００３５】以上のごとく、ソート対象のデータ列をサ
ーチして、ソート不要部分を抽出し、この不要部分から
マージを開始することにより、データ単位からのマージ
処理を省くことができる。この結果、通常はソート不要
部分が大きいから、マージソート処理が大幅に高速化さ
れる。

【００３６】なお、上記マージ処理の方法は１例であ
り、他のマージ処理方式に適用できることは勿論であ
る。

【００３７】

【発明の効果】以上説明したように、本発明は、先ず、
ソート対象のデータ列をサーチして整列処理不要の一連
のデータ列を抽出し、このデータ列を部分集合としてマ
ージ処理を開始するようにしたので、最小データ単位か
らマージ処理を行う従来の方法と比較してマージ処理数
を大幅に省略することができ、処理速度が改善される効
果は極めて大きい。

【図面の簡単な説明】

【図１】 本発明の原理図

【図２】 一実施例の構成図

【図３】 基本動作フローチャート図

【図４】 ソート不要部分抽出処理フローチャート図

【図５】 ソート不要部分抽出処理例を表す図

【図６】 マージソート処理フローチャート図

【図７】 マージソート処理例を表す図

【図８】 従来例のマージソート方法説明図

【符号の説明】

１ 中央処理ユニットＣＰＵ ２ マージソー
ト制御部 ３ データ読込処理部 ４ ソート不要
部抽出処理部 ５ ソート不要部マージ処理部 ６ データ書込
処理部 ７ ファイル装置 ８ メモリ ９ バッファ 10 ソートイン
デックス

Claims (2)

【特許請求の範囲】
1. 【請求項１】 ソート対象のデータ列を検索してソー
   ト処理不要な部分集合を抽出し、この部分集合をソート
   済み並びとして併合する所定のマージ処理を行って、該
   データ列をソートすることを特徴とするマージソート方
   法。
2. 【請求項２】 ソート対象のデータ列を検索してソー
   ト処理不要な部分集合を抽出するソート不要部抽出処理
   部と、 前記部分集合を基準として所定のマージ処理を行うマー
   ジ処理部とを備えることを特徴とするマージソート処理
   装置。