ソート処理方法及びプログラム
【課題】データのソート処理における処理時間を短縮できる技術を提供する。
【解決手段】ソート対象のデータ列（１１）のデータ値を、グループ定義（１０）に従ってグループ化により分割し、グループ単位のデータ列（２１〜２３）を作成する。グループは、対象データ値全範囲を適度な個数（サイズ）で任意に区切ったものであり、構成値により順序付けられている。グループ単位のデータ列（２１〜２３）に対して、個別にソート処理を行った後、すべての列（２４〜２６）をグループ順に結合する。これにより、ソート結果のデータ列(１２)を得る。
【解決手段】ソート対象のデータ列（１１）のデータ値を、グループ定義（１０）に従ってグループ化により分割し、グループ単位のデータ列（２１〜２３）を作成する。グループは、対象データ値全範囲を適度な個数（サイズ）で任意に区切ったものであり、構成値により順序付けられている。グループ単位のデータ列（２１〜２３）に対して、個別にソート処理を行った後、すべての列（２４〜２６）をグループ順に結合する。これにより、ソート結果のデータ列(１２)を得る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ（電子計算機）システムにおけるデータ／情報のソート（整列、並べ替え）処理の技術に関する。
【背景技術】
【０００２】
近年、記憶装置の大容量化、処理装置の高性能化により、端末装置における業務処理等でデータベースが検索される機会が増えている。加えて、インターネットの普及等により、膨大な顧客データベースの管理や、インターネット経由でのデータへのアクセス記録を保存管理する必要が高まり、そのデータ容量も増大していることから、検索処理に要する時間を短縮することが課題となっている。
【０００３】
検索処理は、検索対象となるデータが降順または昇順にソートされていれば処理時間を短縮することができるが、データベースにデータが追加された時点や、さらに任意の時点でのデータのソート処理が、処理装置の負荷を増大させ、業務に大きな影響を与えるケースも少なく無い。
【０００４】
コンピュータ上で管理されるデータベースや、表計算用ソフトウェアで使用する表形式データは、データの検索処理時間の短縮や、業務で必要な集計処理の効率を上げるために、昇順または降順にソートしておくことが必要となる。
【０００５】
一般的に、データベースや、表計算ソフトウェアの表形式データに、新たにデータが追加されたりした場合には、データを降順または昇順に並べ替えるために、データのソート処理が実施される。
【０００６】
そのソート処理の方法として、対象となるデータ列の各データを分解した後、順番に比較・並べ替えを行いつつマージ（併合）していくマージソート法（ソートマージ法などともいう）や、クイックソート法が、広く採用されている。
【０００７】
しかし、上記いずれの方法も、データ量が多くなるにつれ処理時間が長くなる傾向にあり、近年データベースが大容量化していることからも、このソート処理時間の短縮が課題となっている。
【０００８】
特に、データ量が大きく、頻繁にデータベースにデータが追加されるシステムでは、システム利用者の待ち時間短縮やレスポンスを低下させないために、ソート処理時間を短縮し、システムの負荷を軽減することも必要となっている。
【０００９】
従来のソート処理の技術として、特開平８−２２１２５４号公報（特許文献１）には、マージソート方法について記載されている。
【特許文献１】特開平８−２２１２５４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
前述した大量のデータのソート処理時間を短縮し、処理装置の負荷を軽減することは、現在の様々なシステムにおいて、その処理性能を保持または向上するために必要不可欠の課題となっている。特に、ソート処理性能の向上によって、大容量データベースのデータ検索などの処理性能も向上させることが望まれている。
【００１１】
前記従来の技術であるマージソート方法は、マージソート対象データ列のレコード数（データ値個数）をＮとした場合、ソートに要する処理時間は、Ｎ×log(Ｎ)に比例することが一般的に知られている。Ｎが多くなる程、データ列中の値の比較演算処理数（又はマージ処理数）が増加して総処理時間が長くなる。さらに、短時間に複数回連続処理が実行される等の要因により、システムに大きな負荷を与えてしまう場合も多い。
【００１２】
本発明は、以上のような問題に鑑みてなされたものであり、その目的は、データ／情報のソート処理における処理時間を短縮できる技術を提供すること、換言すれば、コンピュータシステムにおけるデータ列のソート処理方法及びプログラムに係わり、特に従来のマージソート法の改良／工夫に基づき効率的なソート処理の技術を提供することである。
【課題を解決するための手段】
【００１３】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。前記目的を達成するために、本発明の技術は、コンピュータシステムで実行されるデータ／情報のソート処理に係わり、以下に示すような技術的手段を備えることを特徴とする。本発明のソート処理方法は、コンピュータ（プロセッサ）が実行する、下記（１−１）〜（１−３）の処理ステップを備える。また、本発明のプログラムは、本発明のソート処理方法に従う処理をコンピュータに実行させるものであり、本ソート処理方法の各処理ステップに対応する処理を行う部分を備える。
【００１４】
元（入力）となるソートされていないデータ、換言すればソート対象となる第１のデータ列（[ｄ１，……，ｄｎ]）がある。本ソート処理によって、第１のデータ列から、その全体がソートされた、ソート結果（出力）のデータ列（後述の第４のデータ列）を得る。処理対象となるデータ列は、複数のデータ値（数値や文字など大小関係を有するもの）による列である。第１のデータ列のデータ値が取り得る値としては、同じ値の重複も有り得るとする。第１のデータ列におけるデータ値個数をｎ、重複せずに取り得るデータ値の個数（要素数）をｐ、ｐに対応するデータ値範囲（順序付けを持つ値の集合）をＳとする。なお、複数の構成要素が順序付きであることを[]で表す。
【００１５】
準備として、第１のデータ列のデータ値範囲（Ｓ）、又はそれを包含する連続するデータ値範囲などを、任意の区切りで分割した、複数（Ｍ個）のグループ（第１〜第Ｍグループ：[Ｇ１，Ｇ２，……，ＧＭ]）を用意する。これらグループ（データ値範囲乃至集合）は、構成値の大小によって順序付けを持って定義される。第１のデータ列の各データ値（例えばレコード値）が前記複数のグループのいずれかに分類が可能なように定義されている必要がある。グループの順序付けは、例えば、各グループを構成するデータ値における最小値（min）や最大値（max）によってなされる。例えば、グループＧｘ内の最小値をＧｘmin、最大値をＧｘmaxとすれば、Ｇ１min＜Ｇ２min＜……＜ＧＭmin、Ｇ１max＜Ｇ２max＜……＜ＧＭmaxである。また、｛Ｇ１max＜Ｇ２min、Ｇ２max＜Ｇ３min、……、Ｇ（Ｍ−１）max＜ＧＭmin｝である。
【００１６】
（１−１） 前記グループ定義をもとに、まず、第１の処理ステップとして、第１のデータ列を、前記複数のグループに従って、グループ単位の複数の第２のデータ列（グループ単位データ列：[Ｇ１列,Ｇ２列,……,ＧＭ列]）へグループ化により分割（分類）する。
【００１７】
（１−２） 次に、第２の処理ステップとして、上記（１−１）で分割された、グループ単位の複数の第２のデータ列に対して、それぞれ個別にソート処理を実行し、グループ単位のソート済みの複数の第３のデータ列（ソート済みグループ単位データ列：[Ｇ１列’,Ｇ２列’,……,ＧＭ列’]）を得る。なお第２及び第３のデータ列も、前記グループの順序付けに対応して順序付けられている。第２の処理ステップでは、各第２のデータ列に対し、従来技術に従う所定のアルゴリズムのソート処理を実行する。また複数の個別のソート処理は、コンピュータシステム構成に応じて、順次処理としても並列処理としてもよい。
【００１８】
（１−３） 次に、第３の処理ステップとして、上記（１−２）でソート済みとなったグループ単位の複数の第３のデータ列について、前記複数のグループの定義における順序付けに従って、順番に結合（連結）する。即ち、該当グループのデータ列内の値を、他グループのデータ列内の値と大小比較することなく、即ち第３のデータ列同士でマージ処理することなく、先頭グループ相当(Ｇ１列’)から末尾グループ相当(ＧＭ列’)までを順番に結合して１つの第４のデータ列とする。これがソート結果（出力）となる。
【００１９】
（２） また例えば、本ソート処理方法では、前記第１のデータ列に対応した前記複数のグループの定義を作成（準備）する処理ステップを有する。本作成のタイミングは、例えば、ソート対象となるデータの形式や特性（ｐ，Ｓなど）が決まっている場合などに、前記グループの定義を、ソート処理の実行よりも事前に取り決めておく。そして、前記複数のグループは、第１のデータ列のデータ値範囲（Ｓ）等を、例えば、要素数（ｐ）等よりも小さい任意のデータ値個数（Ｌ）乃至サイズで区切ってなることを特徴とする。また例えば、前記複数のグループは、第１のデータ列のデータ値範囲（Ｓ）等を、Ｍ個のグループに区切ってなること等としてもよい。
【００２０】
（３） また、本ソート処理方法は、より詳しくは例えば以下である。第１のデータ列に対応した第１の配列と、グループ単位の複数の第２のデータ列に対応した複数の第２の配列とを使用する。前記第１の処理ステップでは、第１の配列を、その先頭のデータ値（ｄ１）から末尾のデータ値(ｄｎ)まで順に、複数のグループの定義に対応した、各グループへの振り分けのためのインデックステーブル等に従って、グループ単位の複数の第２の配列へ振り分けて該当配列内にデータ値を追加格納してゆくことで複数の第２の配列を作成し、前記第２の処理ステップでは、複数の第２の配列を、個別にソート処理し（換言すれば複数のソート済みの配列を得る）、前記第３の処理ステップでは、ソート処理済みの複数の第２の配列を、グループの順序付けに従って１つに結合して第３の配列をソート結果として得ることを特徴とする。
【発明の効果】
【００２１】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。本発明によれば、データ／情報のソート処理における処理時間を短縮することが可能となる。換言すれば、コンピュータシステムにおけるデータ列のソート処理方法及びプログラムに係わり、特に従来のマージソート法の改良／工夫に基づき効率的なソート処理の技術を提供できる。
【００２２】
また特に、グループ単位に分割されてソート処理が完了した各データ列は、他グループのデータ列とデータ値を比較しながらマージ処理する必要が無く、単にグループ順に結合すれば、全体がソートされた一つのデータ列をソート結果として得ることができる。そのため、従来マージソート処理で必要であった併合時の比較処理に要する時間を削減でき、従来マージソート処理よりも効率的なソート処理を提供できる。
【００２３】
これらの効果は、ソート対象データ列の要素数が多いほど大きいため、特に大容量データベースの検索処理を行うコンピュータシステムなどのように、大規模なシステムや装置に適用することで、より大きな効果を期待できる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一部には原則として同一符号を付し、その繰り返しの説明は省略する。図１〜図５は、本実施の形態を示すためのものであり、図６〜図７は、本実施の形態との比較のために従来技術のマージソート処理方法について示すものである。
【００２５】
図１は、本実施の形態のソート処理方法の原理（処理例を含む）を示す。図２は、本ソート処理方法に従った処理を実行するコンピュータシステムの構成を示す。図３は、本コンピュータシステムにおける処理対象となる、ソート対象データ列を含んだデータベースの構成例を示す。図４は、本コンピュータシステムにおける、グループ事前取り決め及び配列使用によるデータ列のソート処理例を示す。図５は、同ソート処理方法における、データ列のソート処理例を示すフローである。
【００２６】
＜従来のマージソート方法＞
まず、本実施の形態との比較のために、従来技術のマージソート方法について説明する。図６は、従来のマージソート方法の処理例を示す。図７は、従来のマージソート方法で用いる一般的な併合（マージ）処理の説明図であり、(ａ)はマージ対象データ列、(ｂ)はマージ結果データ列、(ｃ)はマージ処理のフローを示す。
【００２７】
図６において、マージソート対象データ列（Ｘ１）６００がある。データ列（Ｘ１）６００は、配列を用いて処理される。データ列（Ｘ１）６００は、レコードＮｏが０から７までの各レコードにデータ値が順に格納されている。これら各レコードの８個のデータ値[３，６，８，１，４，７，２，５]を、昇順に並べ替える方法を示す。
【００２８】
まず第１の段階として、まず、レコードＮｏ＝０〜７の８個のデータ値から、データ値の昇順にソート済みの部分データ列を抽出（取り出し）することにより、複数の部分データ列（部分集合）に分解する。本例では、３つの部分データ列（６０１〜６０３）として、[３，６，８]，[１，４，７]，[２，５]が得られる。
【００２９】
次に第２の段階として、抽出された部分データ列（６０１〜６０３）を、２つずつマージ処理してゆく。まず、第１の部分データ列６０１と第２の部分データ列６０２とをマージ＃１（第１（１回目）のマージ処理）する。各マージ処理の手順は、図７で示される。マージ＃１処理により、データ値の昇順に併合された第４の部分データ列６０４を生成する。次に、生成した第４の部分データ列６０４と、最後の第３の部分データ列６０３とを、同様手順でマージ＃２（第２（２回目）のマージ処理）する。これにより、元のデータ列（６００）の内容が昇順に並べ替えられた、１つのマージソート結果データ列（Ｘ２）６０５が得られる。分解された部分データ列がもっと多い場合も、同様のマージ処理の繰り返しによりソート結果が得られる。
【００３０】
図７において、図７（ａ）のＡとＢは、それぞれ、データ値を２つ持ったデータ列を表している。また、図７（ｂ）のＣは、データ値を４つ持ったデータ列であり、換言すれば併合処理結果データ列の格納用バッファ乃至配列を表している。ｉ，ｊ，ｋは、各データ列におけるデータ値の位置インデックス（レコードＮｏなど）である。
【００３１】
一単位の併合処理において、まず、図７（ａ）の第１の比較処理（Ｐ１）で、ＡとＢのそれぞれの先頭（ｉ，ｊ＝０）の値｛２，１｝を比較する。そして、その小さい方の値であるＢの先頭の値｛１｝を、Ｃの先頭（ｋ＝０）の位置に格納する。次に、第２の比較処理（Ｐ２）で、前記Ｐ１で大きい方の値であったＡの先頭の値｛２｝と、Ｂの２番目（ｊ＝１）の値｛７｝とを比較し、その小さい方の値であるＡの先頭の値｛２｝を、Ｃの２番目（ｋ＝１）の位置に格納する。以後同様に、ＡとＢ、各データ列の格納済みの値の次の値を比較の対象とした比較処理を繰り返して、Ｃに順に比較結果値を格納してゆく。即ち、次に、第３の比較処理（Ｐ３）で、前記Ｂの２番目の値｛７｝と、Ａの２番目の値｛６｝とを比較し、その小さい方の値であるＡの２番目の値｛６｝を、Ｃの３番目の位置に格納し、最後に残った値｛７｝を４番目の位置に格納する。これにより、２つのデータ列（Ａ，Ｂ）の併合によりソートされたデータ列がＣとして得られる。
【００３２】
図７（ｃ）において、本マージ処理フローは、前記図７（ａ），（ｂ）のデータ列｛Ａ，Ｂ，Ｃ｝の位置インデックス（ｉ，ｊ，ｋ）に対応している。各データ列｛Ａ，Ｂ，Ｃ｝に対応した配列｛Ａ[ｉ]，Ｂ[ｊ]，Ｃ[ｋ]｝を用いて処理される。
【００３３】
＜本実施の形態のソート方法＞
次に、本実施の形態のソート処理方法及び本方法に従った処理を実行するコンピュータシステムを説明する。本実施の形態のソート処理方法は、前述した従来のマージソート方法を踏まえ、その改良／工夫の結果、従来必要であったマージ処理、特にその値比較処理を削減している。そのため単にソート処理方法と称している。
【００３４】
本実施の形態のソート処理方法によるソート処理が適用されるシステム及びケースとして例えば以下がある。インターネット経由でＰＣ等の端末からサーバ等に接続する利用者に、固有の利用者番号（ユーザＩＤ等）が付与されているとする。その利用者のサーバへの接続記録が、複数の利用者が接続を開始した時刻順に、表形式データ（データベース）として格納されるとする。このデータベースのデータ（インターネット接続記録データ）の横１行を１レコードとして、このレコード群を例えば前記利用者番号の順にソートする処理について考える。図３には、前記インターネット接続記録データであるデータベースの格納データ例を示している。
【００３５】
以下説明する本実施の形態では、上記ケースにおけるソート処理の考え方を簡略化して示すものである。例えばソート対象データ列のレコード数及び値範囲を簡単のため少なくして説明するが、実際には大量データ及び広い値範囲を対象にして同様の考え方で処理可能である。図２に示すコンピュータシステム１００は、図１に示す原理を踏まえ、上記ケースに対応したソート処理を行う機能を備えるものであり、そのソート処理は、図４，図５で示される。
【００３６】
図１において、データ値要素｛Ａ〜Ｊ｝で構成される、元（入力）のデータ列１１（ソート対象データ列：Ｄ１）がある。また、データ列１１に対応するグループ定義１０として、データ列１１が取り得るデータ値範囲であるデータ値要素（範囲）[Ａ〜Ｊ]を、任意のデータ値個数などで区切って成る、順序付けされた複数のグループが準備される。本例では全範囲[Ａ〜Ｊ]をデータ値３個程度で区切ってなる３つのグループ[Ｇ１，Ｇ２，Ｇ３]が準備される。第１のグループＧ１は、含まれるデータ値が｛Ａ〜Ｃ｝であり、同様に、第２のグループＧ２は｛Ｄ〜Ｆ｝、第３のグループＧ３は｛Ｇ〜Ｊ｝が含まれる。グループ内の値によって、Ｇ１，Ｇ２，Ｇ３の順での順序付けを有する。
【００３７】
本ソート処理方法では、まず第１に、データ列(Ｄ１)１１を、グループ定義１０に従って、データ列１１のデータ値のグループ化（グルーピング）により、３つのグループ単位データ列（２１〜２３）に分割する。そして第２に、その分割されたグループ単位データ列（２１〜２３）ごとに、それぞれソート処理（ソート＃１〜＃３）を行う。これにより、各グループに対応した、ソート済みグループ単位データ列（２４〜２６）を得る。そして第３に、これら３つのソート済みグループ単位データ列（２４〜２６）を、前記グループの順序付けに従って、順番に結合する。これにより、元のデータ列１１の全体がソートされた内容である、１つのデータ列１２（ソート結果データ列：Ｄ２）が得られる。
【００３８】
前記グループ化では、データ列１１を、要素｛Ａ〜Ｃ｝で構成されるグループ単位データ列（Ｇ１列）２１、要素｛Ｄ〜Ｆ｝で構成されるグループ単位データ列（Ｇ２列）２２、及び要素｛Ｇ〜Ｊ｝で構成されるグループ単位データ列（Ｇ３列）２３に分割する。例えば、グループ単位データ列（Ｇ１列）２１は、データ列(Ｄ１)１１から、Ｇ１に含まれる値｛Ｂ，Ｃ，Ａ｝（レコードＮｏ＝０，１，４のデータ値）を順に取り出したものである。そして、グループ単位データ列（２１〜２３）ごとに、所定の方法によるソート処理（ソート＃１〜＃３）を行う。これにより、Ｇ１列（２１）がソートされたソート済みグループ単位データ列（ソート済みＧ１列）２４を生成し、同様に、Ｇ２列（２２）がソートされたソート済みＧ２列２５、及びＧ３列（２３）がソートされたソート済みＧ３列２６を生成する。前記グループ単位データ列（２１〜２３）やソート済みグループ単位データ列（２４〜２６）も、グループ定義１０に従って順序付けがされている。最後に、これら３つのソート済みグループ単位データ列（２４〜２６）を順番に即ち２４，２５，２６の順に結合すると、ソートされたデータ列(Ｄ２)１２が得られる。
【００３９】
図２において、本コンピュータシステム１００は、処理装置（ＣＰＵ）１０１、メモリ１０２、記憶装置１０３、入力部１０６、出力部１０７、表示部１０８、通信Ｉ/Ｆ部１０９等を有する構成である。メモリ１０２上には、ソート処理プログラム１１０、ＯＳ１２０、ワークエリア１３０などの領域が確保される。ソート処理プログラム１１０は、データ読込処理部１１１、グループ分割処理部１１２、ソート処理部１１３を有する。
【００４０】
処理装置１０１は、ＯＳ１２０等の他、メモリ１０２上にロードされたソート処理プログラム１１０を実行する。これにより本ソート処理方法に従ったソート処理が実現される。ＯＳ１２０は、コンピュータシステム１００の制御プログラムであり、例えば、データベース処理アプリケーションプログラムなども含む。ワークエリア１３０は、ＯＳ１２０やソート処理プログラム１１０の作業用記憶領域である。
【００４１】
記憶装置１０３は、例えばハードディスクドライブであり、入力データ１０４、結果データ１０５などを記憶する。入力データ１０４は、ソート処理プログラム１１０の入力データとなるソート対象データ列を含む。結果データ１０５は、ソート処理プログラム１１０の出力データとなるソート結果データ列を含む。入力部１０６は、キーボード等のデバイスである。出力部１０７は、プリンタ等のデバイスである。表示部１０８は、ディスプレイ等のデバイスである。これらデバイスはコンピュータシステム１００の管理者などにより操作される。通信Ｉ/Ｆ部１０９は、インターネット等のネットワークに接続され通信処理を行う部分である。
【００４２】
前記インターネット接続記録データは、例えば、通信Ｉ/Ｆ部１０９を介して、記憶装置１０３内のデータベースに格納される。ソート処理プログラム１１０は、必要に応じて、記憶装置１０３からメモリ１０２上に入力データ１０４を読み込み、ソート処理を実行して、その結果データ１０５を、記憶装置１０３内に格納する。
【００４３】
コンピュータシステム１００におけるソート処理の際、処理装置１０１及びメモリ１０２上のＯＳ１２０とソート処理プログラム１１０のデータ読込処理部１１１により、まず、入力データ１０４をワークエリア１３０に読み込む。読み込まれたデータ（データ列）は、グループ分割処理部１１２により、グループ単位データ列へと分割（グループ化）処理される。そして、ソート処理部１１３により各グループ単位データ列がソート処理された後、グループ順に結合され、結果データ１０５として記録される。結果データ１０５は、キーボード等の入力部１０６の操作などに応じて、ディスプレイである表示部１０８へ表示されたり、プリンタ等の出力部１０７に出力されたりする。
【００４４】
図３のデータベースにおいて、例として、接続開始時刻３１、接続終了時刻３２、利用者名３３、利用者番号３４、メールアドレス３５などの情報が管理されている。利用者番号３４の項目（列）の各値が、ソート対象データ列の各レコードのデータ値に対応する。ここでは利用者番号３４を数字としているが、英字など他の情報でも構わない。ソート対象データ列１１のデータ値は、重複する場合もしない場合もある。本データベースを利用者番号３４で予めソートしておくことによって、利用者番号３４を用いたデータベース検索処理が効率化されることになる。
【００４５】
図４及び図５において、本コンピュータシステム１００及びソート処理方法における具体的なソート処理の動作及び流れを示している。図５に示すフローは、図４における処理例に対応している。以下、図４及び図５において、元のデータ列４１（ソート対象データ列配列：Ａ１）における８レコード[３，６，８，１，４，７，２，５]を昇順に並べ替えてデータ列４２[１〜８]を得るソート処理を例に用いて動作を説明する。
【００４６】
まず準備として、本実施の形態の一つの特徴である、元のデータ列４１のグループ化、即ち複数のグループに分割（分類）するためのグループ定義４０を、事前の取り決めとして行っておく。即ちコンピュータシステム１００上で、ソート処理の実行よりも前に、対象データの形式や特性に応じたグループ定義４０を作成しておく。図４に示す本例では、グループ定義４０として、データ列４１が取り得る全データ値範囲[１〜８]を、データ値個数（Ｌ）３個程度で区切って、グループ数（Ｍ）が３つのグループ[Ｇ１，Ｇ２，Ｇ３]に分けている。即ちソート対象となるデータ列４１のレコードのデータ値において、値｛１〜３｝を第１のグループＧ１、値｛４〜６｝を第２のグループＧ２、値｛７，８｝を第３のグループＧ３とする。これらは、構成値の大小によって、Ｇ１，Ｇ２，Ｇ３の順に順序付けられて定義されている。条件としては、あるグループＧｘ内の最小値が１つ前のグループＧ（ｘ−１）内の最大値より大きく、かつ、グループＧｘ内の最大値が１つ後のグループＧ（ｘ＋１）内の最小値より小さくなるように取り決める必要がある。
【００４７】
グループ分割処理部１１２におけるグループ単位への分割処理では、データ列４１の各データ値を、グループ定義４０に従い、グループ[Ｇ１，Ｇ２，Ｇ３]に対応した、グループ単位配列（４０６〜４０８）に振り分けする。グループＧ１に含まれるデータ値に対してはＧ１配列４０１へ、といったように、メモリ１０２上に必要な配列が確保されて処理される。
【００４８】
なお、本ソート処理方法を実装しているソート処理プログラム１１０では、図５のフローのＳ５０２とＳ５０３に示すように、グループ定義４０の各グループへのデータ列１１の各データ値の振り分け判定及び振り分け処理のための所定のアルゴリズムが組み込まれる。このアルゴリズムは、例えば、グループ定義４０に対応して予め準備した、データ値ごとのインデックステーブルを参照して各データ値をグループ単位へ振り分ける方法（従来技術）等を用いる。
【００４９】
ソート動作を説明する。まず、グループ化処理として、図４のデータ列４１が、レコード読み込みにより、各グループ単位配列（４０６〜４０８）へと振り分けされる。図５のＳ５０１のレコード読み込み処理により、最初に、データ列４１におけるレコードＮｏ＝０のデータ値｛３｝が読み込まれる。Ｓ５０２とＳ５０３において、読み込まれたレコード値｛３｝が、Ｇ１〜Ｇ３のどのグループに属するかが判定される。この判定の結果、Ｓ５０２で、値｛３｝はＧ１に属すると判断され、Ｓ５０４により、Ｇ１配列４０１の末尾に、読み込まれた値｛３｝が追加される。なお実際には新たにＧ１配列４０１が作成される。Ｓ５０７では、次に続くレコードが存在するので、Ｓ５０１〜Ｓ５０６の処理をループする。
【００５０】
次に、Ｓ５０１で、レコードＮｏ＝１のデータ値｛６｝が読み込まれ、Ｓ５０２で、入力値｛６｝はＧ２に属すると判断され、Ｓ５０５により、Ｇ２配列４０２に値｛６｝が追加される。次に、Ｓ５０１で、レコードＮｏ＝２のデータ値｛８｝が読み込まれ、Ｓ５０３及びＳ５０６で、入力値｛８｝はＧ３に属すると判断され、Ｇ３配列４０３の末尾に値｛８｝が追加される。以下同様に、レコードＮｏ＝３〜７について同様の処理を繰り返し、データ列４１の各レコードのデータ値が、各グループ用の配列（４０６〜４０８）に振り分けられる。結果、Ｇ１配列４０７は[３，１，２]となり、Ｇ２配列４０８は[６，４，５]となり、Ｇ３配列４０６は[８，７]となる。
【００５１】
次に、Ｓ５０７で次に続くレコードが存在しないので、Ｓ５０８で、グループ単位配列（４０６〜４０８）について、それぞれ並べ替え、即ち個別のソート処理（ソート＃１〜ソート＃３）を実行する。この際のソート処理アルゴリズムは、既存のものを使用可能である。
【００５２】
グループ単位配列（４０６〜４０８）の各ソート処理（Ｓ５０８）により、ソート済みグループ単位配列（４０９〜４１１）が得られる。即ち、Ｇ１配列４１０は[１，２，３]となり、Ｇ２配列４１１は[４，５，６]となり、Ｇ３配列４０９は[７，８]となる。
【００５３】
最後に、Ｓ５０９の処理により、３つのソート済みグループ単位配列（４０９〜４１１）を、グループ順（Ｇ１−Ｇ２−Ｇ３）に結合する。なお、グループ単位データ列の結合処理は、広い意味ではマージ処理と言えるが、狭い意味では単なる結合であり、その処理負荷は小さい。最終的に、元のデータ列４１を正確に昇順に並べ替えたものに相当するデータ列４２（ソート結果データ列配列：Ａ２）を得ることができる。
【００５４】
前記グループ定義４０及びグループ化について補足する。前記図３では、グループ定義４０として、データ列４１に対応した全範囲[１〜８]に対し、データ値個数（Ｌ）３個程度で区切って３つ（Ｍ）のグループ[Ｇ１，Ｇ２，Ｇ３]を定義している。グループ定義４０におけるグループ数（Ｍ）、グループを構成するデータ値個数（Ｌ）などの内容（変数）について変動させても構わない。実際の処理においては、Ｍ、Ｌなどについては任意に決めてよい。即ち、処理対象データの実データレコード数や実データサイズなどをもとに、処理性能などの点を考慮して適度となるように取り決める。例えば、個別のソート処理に対応して適度なサイズのデータ値個数（Ｌ）で区切る。グループ単位の個別のソート処理は、Ｌに対して高速となるものを選択すれば望ましい。
【００５５】
例えば、本ソート処理実行時に、データ列４１の値の取り得る全範囲が[１〜１０００]の場合に、Ｌ＝１００で区切ってＭ＝１０個のグループ[Ｇ１〜Ｇ１０]とする。また例えば、データ列４１のデータ値が英文字列である場合に、文字列先頭文字が｛ａ〜ｅ｝ならばＧ１、｛ｆ〜ｋ｝ならばＧ２、｛ｌ〜ｐ｝ならばＧ３といったように、予め適切に取り決めておけばよい。その他、対象データに応じて適宜、グループ定義４０を変更したり使い分けたりしても構わない。
【００５６】
以上のように、本ソート処理方法では、グループ順に分割されたデータ列を結合するのみで、元のデータ列がソートされた結果を得ることが可能なグループを定義している。そのため、グループ単位データ列に分割して個別ソートした結果をグループ順に結合することで、図７に示すような従来のマージ処理及びその値比較処理を省略することができる。従って、特に値比較処理を要さない分、総合的なソート処理性能の向上が期待できる。
【００５７】
図７に図６のマージソート処理の一部処理であるマージ処理を示しているが、このマージ処理は、マージ対象データ列の長さが大きくなる程、値の比較回数が増加する。この処理時間は、データ列中のデータ値個数（レコード数）をＮとした場合、Ｎ×log(Ｎ)に比例することが一般的に知られており、Ｎが多くなる程その処理性能は劣化する。
【００５８】
一方、本実施の形態におけるソート処理時間（グループ単位のソート処理を順次に実行する場合）は、ソート対象データ列のデータ値個数Ｎをグループ数Ｍで分割した場合に、Ｍ×(Ｎ/Ｍ)×log(Ｎ/Ｍ)＝Ｎ×log(Ｎ/Ｍ)となる。データ値個数Ｎが多くなるほど、従来処理に比較して処理性能を大きく改善することができる。なおここで考慮しなければならない点として、従来のマージソート処理と、本実施の形態の処理とにおける、ソート対象データを分割するための処理時間があるが、従来処理（ソート済み列の抽出処理）では単純にデータ列中の各データ値の次データ値との大小比較回数(Ｎ−１)に比例する。しかし本実施の形態における処理では、ソート対象データ列中の各データ値をグループ化（振り分け）するために、前記インデックステーブルを用いる方法などのいくつかの方法／手段が考えられる。そのため、従来のマージソート処理と単純には比較できないが、本来のソート処理に要する時間の差に大きな影響を与えることは無い。
【００５９】
従来のマージソート処理方法と本ソート処理方法との効果を比較する。前記Ｎ×log(Ｎ)とＮ×log(Ｎ/Ｍ)とを具体的な値で比較する。データ値個数Ｎのレコードから成る元のデータ列を、Ｍ＝１０個のグループ[Ｇ１〜Ｇ１０]で分割した場合、処理時間は以下のように見積もることができる。まずＮ＝100の場合、Ｎ×log(Ｎ)＝100×6.64＝664であり、Ｎ×log(Ｎ/Ｍ)＝100×3.32＝332である。これらを比較すると、332/664＝1/2であり、従来の約半分の処理時間で済むことが期待できる。また、Ｎ＝1000の場合、Ｎ×log(Ｎ)＝1000×9.97＝9970であり、Ｎ×log(Ｎ/Ｍ)＝1000×6.64=6640である。比較すると、6640/9970≒2/3である。また、Ｎ=10000の場合、Ｎ×log(Ｎ)＝10000×13.29＝132900であり、Ｎ×log(Ｎ/Ｍ)＝10000×9.97＝99700である。比較すると、99700/132900＝0.75≒3/4である。
【００６０】
以上から、本実施の形態によるソート処理方法及びそのソート処理プログラム１１０でのソート処理は、従来のマージソート処理と比較して、処理時間を短縮することが可能である。
【００６１】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【産業上の利用可能性】
【００６２】
本発明は、ソート処理を用いる情報処理システム全般に利用可能であり、特にデータベース検索処理システムなどにも有効である。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施の形態のソート処理方法の原理を示す説明図である。
【図２】本発明の一実施の形態のソート処理方法に従った処理を実行するコンピュータシステムの構成を示す図である。
【図３】本発明の一実施の形態のソート処理方法に従った処理を実行するコンピュータシステムにおける、ソート対象データ列を含んだデータベースの構成例を示す図である。
【図４】本発明の一実施の形態のソート処理方法におけるデータ列のソート処理例を示す説明図である。
【図５】本発明の一実施の形態のソート処理方法におけるデータ列のソート処理例を示すフローチャートである。
【図６】従来のマージソート方法の処理例を示す説明図である。
【図７】従来のマージソート方法で用いる一般的な併合（マージ）処理の説明図であり、(ａ)はマージ対象データ列、(ｂ)はマージ結果データ列、(ｃ)はマージ処理のフローチャートを示す。
【符号の説明】
【００６４】
１０，４０…グループ定義、１１…データ列（ソート対象データ列）、１２…データ列（ソート結果データ列）、２１〜２３…グループ単位データ列、２４〜２６…ソート済みグループ単位データ列、４１…配列（ソート対象データ列配列）、４２…配列（ソート結果データ列配列）、１００…コンピュータシステム、１０１…処理装置（ＣＰＵ）、１０２…メモリ、１０３…記憶装置、１０４…入力データ、１０５…結果データ、１０６…入力部、１０７…出力部、１０８…表示部、１０９…通信Ｉ/Ｆ部、１１０…ソート処理プログラム、１１１…データ読込処理部、１１２…グループ分割処理部、１１３…ソート処理部、１２０…ＯＳ、１３０…ワークエリア、４０１〜４１１…配列、６００…マージソート対象データ列、６０１〜６０４…データ列、６０５…マージソート結果データ列。
【技術分野】
【０００１】
本発明は、コンピュータ（電子計算機）システムにおけるデータ／情報のソート（整列、並べ替え）処理の技術に関する。
【背景技術】
【０００２】
近年、記憶装置の大容量化、処理装置の高性能化により、端末装置における業務処理等でデータベースが検索される機会が増えている。加えて、インターネットの普及等により、膨大な顧客データベースの管理や、インターネット経由でのデータへのアクセス記録を保存管理する必要が高まり、そのデータ容量も増大していることから、検索処理に要する時間を短縮することが課題となっている。
【０００３】
検索処理は、検索対象となるデータが降順または昇順にソートされていれば処理時間を短縮することができるが、データベースにデータが追加された時点や、さらに任意の時点でのデータのソート処理が、処理装置の負荷を増大させ、業務に大きな影響を与えるケースも少なく無い。
【０００４】
コンピュータ上で管理されるデータベースや、表計算用ソフトウェアで使用する表形式データは、データの検索処理時間の短縮や、業務で必要な集計処理の効率を上げるために、昇順または降順にソートしておくことが必要となる。
【０００５】
一般的に、データベースや、表計算ソフトウェアの表形式データに、新たにデータが追加されたりした場合には、データを降順または昇順に並べ替えるために、データのソート処理が実施される。
【０００６】
そのソート処理の方法として、対象となるデータ列の各データを分解した後、順番に比較・並べ替えを行いつつマージ（併合）していくマージソート法（ソートマージ法などともいう）や、クイックソート法が、広く採用されている。
【０００７】
しかし、上記いずれの方法も、データ量が多くなるにつれ処理時間が長くなる傾向にあり、近年データベースが大容量化していることからも、このソート処理時間の短縮が課題となっている。
【０００８】
特に、データ量が大きく、頻繁にデータベースにデータが追加されるシステムでは、システム利用者の待ち時間短縮やレスポンスを低下させないために、ソート処理時間を短縮し、システムの負荷を軽減することも必要となっている。
【０００９】
従来のソート処理の技術として、特開平８−２２１２５４号公報（特許文献１）には、マージソート方法について記載されている。
【特許文献１】特開平８−２２１２５４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
前述した大量のデータのソート処理時間を短縮し、処理装置の負荷を軽減することは、現在の様々なシステムにおいて、その処理性能を保持または向上するために必要不可欠の課題となっている。特に、ソート処理性能の向上によって、大容量データベースのデータ検索などの処理性能も向上させることが望まれている。
【００１１】
前記従来の技術であるマージソート方法は、マージソート対象データ列のレコード数（データ値個数）をＮとした場合、ソートに要する処理時間は、Ｎ×log(Ｎ)に比例することが一般的に知られている。Ｎが多くなる程、データ列中の値の比較演算処理数（又はマージ処理数）が増加して総処理時間が長くなる。さらに、短時間に複数回連続処理が実行される等の要因により、システムに大きな負荷を与えてしまう場合も多い。
【００１２】
本発明は、以上のような問題に鑑みてなされたものであり、その目的は、データ／情報のソート処理における処理時間を短縮できる技術を提供すること、換言すれば、コンピュータシステムにおけるデータ列のソート処理方法及びプログラムに係わり、特に従来のマージソート法の改良／工夫に基づき効率的なソート処理の技術を提供することである。
【課題を解決するための手段】
【００１３】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。前記目的を達成するために、本発明の技術は、コンピュータシステムで実行されるデータ／情報のソート処理に係わり、以下に示すような技術的手段を備えることを特徴とする。本発明のソート処理方法は、コンピュータ（プロセッサ）が実行する、下記（１−１）〜（１−３）の処理ステップを備える。また、本発明のプログラムは、本発明のソート処理方法に従う処理をコンピュータに実行させるものであり、本ソート処理方法の各処理ステップに対応する処理を行う部分を備える。
【００１４】
元（入力）となるソートされていないデータ、換言すればソート対象となる第１のデータ列（[ｄ１，……，ｄｎ]）がある。本ソート処理によって、第１のデータ列から、その全体がソートされた、ソート結果（出力）のデータ列（後述の第４のデータ列）を得る。処理対象となるデータ列は、複数のデータ値（数値や文字など大小関係を有するもの）による列である。第１のデータ列のデータ値が取り得る値としては、同じ値の重複も有り得るとする。第１のデータ列におけるデータ値個数をｎ、重複せずに取り得るデータ値の個数（要素数）をｐ、ｐに対応するデータ値範囲（順序付けを持つ値の集合）をＳとする。なお、複数の構成要素が順序付きであることを[]で表す。
【００１５】
準備として、第１のデータ列のデータ値範囲（Ｓ）、又はそれを包含する連続するデータ値範囲などを、任意の区切りで分割した、複数（Ｍ個）のグループ（第１〜第Ｍグループ：[Ｇ１，Ｇ２，……，ＧＭ]）を用意する。これらグループ（データ値範囲乃至集合）は、構成値の大小によって順序付けを持って定義される。第１のデータ列の各データ値（例えばレコード値）が前記複数のグループのいずれかに分類が可能なように定義されている必要がある。グループの順序付けは、例えば、各グループを構成するデータ値における最小値（min）や最大値（max）によってなされる。例えば、グループＧｘ内の最小値をＧｘmin、最大値をＧｘmaxとすれば、Ｇ１min＜Ｇ２min＜……＜ＧＭmin、Ｇ１max＜Ｇ２max＜……＜ＧＭmaxである。また、｛Ｇ１max＜Ｇ２min、Ｇ２max＜Ｇ３min、……、Ｇ（Ｍ−１）max＜ＧＭmin｝である。
【００１６】
（１−１） 前記グループ定義をもとに、まず、第１の処理ステップとして、第１のデータ列を、前記複数のグループに従って、グループ単位の複数の第２のデータ列（グループ単位データ列：[Ｇ１列,Ｇ２列,……,ＧＭ列]）へグループ化により分割（分類）する。
【００１７】
（１−２） 次に、第２の処理ステップとして、上記（１−１）で分割された、グループ単位の複数の第２のデータ列に対して、それぞれ個別にソート処理を実行し、グループ単位のソート済みの複数の第３のデータ列（ソート済みグループ単位データ列：[Ｇ１列’,Ｇ２列’,……,ＧＭ列’]）を得る。なお第２及び第３のデータ列も、前記グループの順序付けに対応して順序付けられている。第２の処理ステップでは、各第２のデータ列に対し、従来技術に従う所定のアルゴリズムのソート処理を実行する。また複数の個別のソート処理は、コンピュータシステム構成に応じて、順次処理としても並列処理としてもよい。
【００１８】
（１−３） 次に、第３の処理ステップとして、上記（１−２）でソート済みとなったグループ単位の複数の第３のデータ列について、前記複数のグループの定義における順序付けに従って、順番に結合（連結）する。即ち、該当グループのデータ列内の値を、他グループのデータ列内の値と大小比較することなく、即ち第３のデータ列同士でマージ処理することなく、先頭グループ相当(Ｇ１列’)から末尾グループ相当(ＧＭ列’)までを順番に結合して１つの第４のデータ列とする。これがソート結果（出力）となる。
【００１９】
（２） また例えば、本ソート処理方法では、前記第１のデータ列に対応した前記複数のグループの定義を作成（準備）する処理ステップを有する。本作成のタイミングは、例えば、ソート対象となるデータの形式や特性（ｐ，Ｓなど）が決まっている場合などに、前記グループの定義を、ソート処理の実行よりも事前に取り決めておく。そして、前記複数のグループは、第１のデータ列のデータ値範囲（Ｓ）等を、例えば、要素数（ｐ）等よりも小さい任意のデータ値個数（Ｌ）乃至サイズで区切ってなることを特徴とする。また例えば、前記複数のグループは、第１のデータ列のデータ値範囲（Ｓ）等を、Ｍ個のグループに区切ってなること等としてもよい。
【００２０】
（３） また、本ソート処理方法は、より詳しくは例えば以下である。第１のデータ列に対応した第１の配列と、グループ単位の複数の第２のデータ列に対応した複数の第２の配列とを使用する。前記第１の処理ステップでは、第１の配列を、その先頭のデータ値（ｄ１）から末尾のデータ値(ｄｎ)まで順に、複数のグループの定義に対応した、各グループへの振り分けのためのインデックステーブル等に従って、グループ単位の複数の第２の配列へ振り分けて該当配列内にデータ値を追加格納してゆくことで複数の第２の配列を作成し、前記第２の処理ステップでは、複数の第２の配列を、個別にソート処理し（換言すれば複数のソート済みの配列を得る）、前記第３の処理ステップでは、ソート処理済みの複数の第２の配列を、グループの順序付けに従って１つに結合して第３の配列をソート結果として得ることを特徴とする。
【発明の効果】
【００２１】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。本発明によれば、データ／情報のソート処理における処理時間を短縮することが可能となる。換言すれば、コンピュータシステムにおけるデータ列のソート処理方法及びプログラムに係わり、特に従来のマージソート法の改良／工夫に基づき効率的なソート処理の技術を提供できる。
【００２２】
また特に、グループ単位に分割されてソート処理が完了した各データ列は、他グループのデータ列とデータ値を比較しながらマージ処理する必要が無く、単にグループ順に結合すれば、全体がソートされた一つのデータ列をソート結果として得ることができる。そのため、従来マージソート処理で必要であった併合時の比較処理に要する時間を削減でき、従来マージソート処理よりも効率的なソート処理を提供できる。
【００２３】
これらの効果は、ソート対象データ列の要素数が多いほど大きいため、特に大容量データベースの検索処理を行うコンピュータシステムなどのように、大規模なシステムや装置に適用することで、より大きな効果を期待できる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一部には原則として同一符号を付し、その繰り返しの説明は省略する。図１〜図５は、本実施の形態を示すためのものであり、図６〜図７は、本実施の形態との比較のために従来技術のマージソート処理方法について示すものである。
【００２５】
図１は、本実施の形態のソート処理方法の原理（処理例を含む）を示す。図２は、本ソート処理方法に従った処理を実行するコンピュータシステムの構成を示す。図３は、本コンピュータシステムにおける処理対象となる、ソート対象データ列を含んだデータベースの構成例を示す。図４は、本コンピュータシステムにおける、グループ事前取り決め及び配列使用によるデータ列のソート処理例を示す。図５は、同ソート処理方法における、データ列のソート処理例を示すフローである。
【００２６】
＜従来のマージソート方法＞
まず、本実施の形態との比較のために、従来技術のマージソート方法について説明する。図６は、従来のマージソート方法の処理例を示す。図７は、従来のマージソート方法で用いる一般的な併合（マージ）処理の説明図であり、(ａ)はマージ対象データ列、(ｂ)はマージ結果データ列、(ｃ)はマージ処理のフローを示す。
【００２７】
図６において、マージソート対象データ列（Ｘ１）６００がある。データ列（Ｘ１）６００は、配列を用いて処理される。データ列（Ｘ１）６００は、レコードＮｏが０から７までの各レコードにデータ値が順に格納されている。これら各レコードの８個のデータ値[３，６，８，１，４，７，２，５]を、昇順に並べ替える方法を示す。
【００２８】
まず第１の段階として、まず、レコードＮｏ＝０〜７の８個のデータ値から、データ値の昇順にソート済みの部分データ列を抽出（取り出し）することにより、複数の部分データ列（部分集合）に分解する。本例では、３つの部分データ列（６０１〜６０３）として、[３，６，８]，[１，４，７]，[２，５]が得られる。
【００２９】
次に第２の段階として、抽出された部分データ列（６０１〜６０３）を、２つずつマージ処理してゆく。まず、第１の部分データ列６０１と第２の部分データ列６０２とをマージ＃１（第１（１回目）のマージ処理）する。各マージ処理の手順は、図７で示される。マージ＃１処理により、データ値の昇順に併合された第４の部分データ列６０４を生成する。次に、生成した第４の部分データ列６０４と、最後の第３の部分データ列６０３とを、同様手順でマージ＃２（第２（２回目）のマージ処理）する。これにより、元のデータ列（６００）の内容が昇順に並べ替えられた、１つのマージソート結果データ列（Ｘ２）６０５が得られる。分解された部分データ列がもっと多い場合も、同様のマージ処理の繰り返しによりソート結果が得られる。
【００３０】
図７において、図７（ａ）のＡとＢは、それぞれ、データ値を２つ持ったデータ列を表している。また、図７（ｂ）のＣは、データ値を４つ持ったデータ列であり、換言すれば併合処理結果データ列の格納用バッファ乃至配列を表している。ｉ，ｊ，ｋは、各データ列におけるデータ値の位置インデックス（レコードＮｏなど）である。
【００３１】
一単位の併合処理において、まず、図７（ａ）の第１の比較処理（Ｐ１）で、ＡとＢのそれぞれの先頭（ｉ，ｊ＝０）の値｛２，１｝を比較する。そして、その小さい方の値であるＢの先頭の値｛１｝を、Ｃの先頭（ｋ＝０）の位置に格納する。次に、第２の比較処理（Ｐ２）で、前記Ｐ１で大きい方の値であったＡの先頭の値｛２｝と、Ｂの２番目（ｊ＝１）の値｛７｝とを比較し、その小さい方の値であるＡの先頭の値｛２｝を、Ｃの２番目（ｋ＝１）の位置に格納する。以後同様に、ＡとＢ、各データ列の格納済みの値の次の値を比較の対象とした比較処理を繰り返して、Ｃに順に比較結果値を格納してゆく。即ち、次に、第３の比較処理（Ｐ３）で、前記Ｂの２番目の値｛７｝と、Ａの２番目の値｛６｝とを比較し、その小さい方の値であるＡの２番目の値｛６｝を、Ｃの３番目の位置に格納し、最後に残った値｛７｝を４番目の位置に格納する。これにより、２つのデータ列（Ａ，Ｂ）の併合によりソートされたデータ列がＣとして得られる。
【００３２】
図７（ｃ）において、本マージ処理フローは、前記図７（ａ），（ｂ）のデータ列｛Ａ，Ｂ，Ｃ｝の位置インデックス（ｉ，ｊ，ｋ）に対応している。各データ列｛Ａ，Ｂ，Ｃ｝に対応した配列｛Ａ[ｉ]，Ｂ[ｊ]，Ｃ[ｋ]｝を用いて処理される。
【００３３】
＜本実施の形態のソート方法＞
次に、本実施の形態のソート処理方法及び本方法に従った処理を実行するコンピュータシステムを説明する。本実施の形態のソート処理方法は、前述した従来のマージソート方法を踏まえ、その改良／工夫の結果、従来必要であったマージ処理、特にその値比較処理を削減している。そのため単にソート処理方法と称している。
【００３４】
本実施の形態のソート処理方法によるソート処理が適用されるシステム及びケースとして例えば以下がある。インターネット経由でＰＣ等の端末からサーバ等に接続する利用者に、固有の利用者番号（ユーザＩＤ等）が付与されているとする。その利用者のサーバへの接続記録が、複数の利用者が接続を開始した時刻順に、表形式データ（データベース）として格納されるとする。このデータベースのデータ（インターネット接続記録データ）の横１行を１レコードとして、このレコード群を例えば前記利用者番号の順にソートする処理について考える。図３には、前記インターネット接続記録データであるデータベースの格納データ例を示している。
【００３５】
以下説明する本実施の形態では、上記ケースにおけるソート処理の考え方を簡略化して示すものである。例えばソート対象データ列のレコード数及び値範囲を簡単のため少なくして説明するが、実際には大量データ及び広い値範囲を対象にして同様の考え方で処理可能である。図２に示すコンピュータシステム１００は、図１に示す原理を踏まえ、上記ケースに対応したソート処理を行う機能を備えるものであり、そのソート処理は、図４，図５で示される。
【００３６】
図１において、データ値要素｛Ａ〜Ｊ｝で構成される、元（入力）のデータ列１１（ソート対象データ列：Ｄ１）がある。また、データ列１１に対応するグループ定義１０として、データ列１１が取り得るデータ値範囲であるデータ値要素（範囲）[Ａ〜Ｊ]を、任意のデータ値個数などで区切って成る、順序付けされた複数のグループが準備される。本例では全範囲[Ａ〜Ｊ]をデータ値３個程度で区切ってなる３つのグループ[Ｇ１，Ｇ２，Ｇ３]が準備される。第１のグループＧ１は、含まれるデータ値が｛Ａ〜Ｃ｝であり、同様に、第２のグループＧ２は｛Ｄ〜Ｆ｝、第３のグループＧ３は｛Ｇ〜Ｊ｝が含まれる。グループ内の値によって、Ｇ１，Ｇ２，Ｇ３の順での順序付けを有する。
【００３７】
本ソート処理方法では、まず第１に、データ列(Ｄ１)１１を、グループ定義１０に従って、データ列１１のデータ値のグループ化（グルーピング）により、３つのグループ単位データ列（２１〜２３）に分割する。そして第２に、その分割されたグループ単位データ列（２１〜２３）ごとに、それぞれソート処理（ソート＃１〜＃３）を行う。これにより、各グループに対応した、ソート済みグループ単位データ列（２４〜２６）を得る。そして第３に、これら３つのソート済みグループ単位データ列（２４〜２６）を、前記グループの順序付けに従って、順番に結合する。これにより、元のデータ列１１の全体がソートされた内容である、１つのデータ列１２（ソート結果データ列：Ｄ２）が得られる。
【００３８】
前記グループ化では、データ列１１を、要素｛Ａ〜Ｃ｝で構成されるグループ単位データ列（Ｇ１列）２１、要素｛Ｄ〜Ｆ｝で構成されるグループ単位データ列（Ｇ２列）２２、及び要素｛Ｇ〜Ｊ｝で構成されるグループ単位データ列（Ｇ３列）２３に分割する。例えば、グループ単位データ列（Ｇ１列）２１は、データ列(Ｄ１)１１から、Ｇ１に含まれる値｛Ｂ，Ｃ，Ａ｝（レコードＮｏ＝０，１，４のデータ値）を順に取り出したものである。そして、グループ単位データ列（２１〜２３）ごとに、所定の方法によるソート処理（ソート＃１〜＃３）を行う。これにより、Ｇ１列（２１）がソートされたソート済みグループ単位データ列（ソート済みＧ１列）２４を生成し、同様に、Ｇ２列（２２）がソートされたソート済みＧ２列２５、及びＧ３列（２３）がソートされたソート済みＧ３列２６を生成する。前記グループ単位データ列（２１〜２３）やソート済みグループ単位データ列（２４〜２６）も、グループ定義１０に従って順序付けがされている。最後に、これら３つのソート済みグループ単位データ列（２４〜２６）を順番に即ち２４，２５，２６の順に結合すると、ソートされたデータ列(Ｄ２)１２が得られる。
【００３９】
図２において、本コンピュータシステム１００は、処理装置（ＣＰＵ）１０１、メモリ１０２、記憶装置１０３、入力部１０６、出力部１０７、表示部１０８、通信Ｉ/Ｆ部１０９等を有する構成である。メモリ１０２上には、ソート処理プログラム１１０、ＯＳ１２０、ワークエリア１３０などの領域が確保される。ソート処理プログラム１１０は、データ読込処理部１１１、グループ分割処理部１１２、ソート処理部１１３を有する。
【００４０】
処理装置１０１は、ＯＳ１２０等の他、メモリ１０２上にロードされたソート処理プログラム１１０を実行する。これにより本ソート処理方法に従ったソート処理が実現される。ＯＳ１２０は、コンピュータシステム１００の制御プログラムであり、例えば、データベース処理アプリケーションプログラムなども含む。ワークエリア１３０は、ＯＳ１２０やソート処理プログラム１１０の作業用記憶領域である。
【００４１】
記憶装置１０３は、例えばハードディスクドライブであり、入力データ１０４、結果データ１０５などを記憶する。入力データ１０４は、ソート処理プログラム１１０の入力データとなるソート対象データ列を含む。結果データ１０５は、ソート処理プログラム１１０の出力データとなるソート結果データ列を含む。入力部１０６は、キーボード等のデバイスである。出力部１０７は、プリンタ等のデバイスである。表示部１０８は、ディスプレイ等のデバイスである。これらデバイスはコンピュータシステム１００の管理者などにより操作される。通信Ｉ/Ｆ部１０９は、インターネット等のネットワークに接続され通信処理を行う部分である。
【００４２】
前記インターネット接続記録データは、例えば、通信Ｉ/Ｆ部１０９を介して、記憶装置１０３内のデータベースに格納される。ソート処理プログラム１１０は、必要に応じて、記憶装置１０３からメモリ１０２上に入力データ１０４を読み込み、ソート処理を実行して、その結果データ１０５を、記憶装置１０３内に格納する。
【００４３】
コンピュータシステム１００におけるソート処理の際、処理装置１０１及びメモリ１０２上のＯＳ１２０とソート処理プログラム１１０のデータ読込処理部１１１により、まず、入力データ１０４をワークエリア１３０に読み込む。読み込まれたデータ（データ列）は、グループ分割処理部１１２により、グループ単位データ列へと分割（グループ化）処理される。そして、ソート処理部１１３により各グループ単位データ列がソート処理された後、グループ順に結合され、結果データ１０５として記録される。結果データ１０５は、キーボード等の入力部１０６の操作などに応じて、ディスプレイである表示部１０８へ表示されたり、プリンタ等の出力部１０７に出力されたりする。
【００４４】
図３のデータベースにおいて、例として、接続開始時刻３１、接続終了時刻３２、利用者名３３、利用者番号３４、メールアドレス３５などの情報が管理されている。利用者番号３４の項目（列）の各値が、ソート対象データ列の各レコードのデータ値に対応する。ここでは利用者番号３４を数字としているが、英字など他の情報でも構わない。ソート対象データ列１１のデータ値は、重複する場合もしない場合もある。本データベースを利用者番号３４で予めソートしておくことによって、利用者番号３４を用いたデータベース検索処理が効率化されることになる。
【００４５】
図４及び図５において、本コンピュータシステム１００及びソート処理方法における具体的なソート処理の動作及び流れを示している。図５に示すフローは、図４における処理例に対応している。以下、図４及び図５において、元のデータ列４１（ソート対象データ列配列：Ａ１）における８レコード[３，６，８，１，４，７，２，５]を昇順に並べ替えてデータ列４２[１〜８]を得るソート処理を例に用いて動作を説明する。
【００４６】
まず準備として、本実施の形態の一つの特徴である、元のデータ列４１のグループ化、即ち複数のグループに分割（分類）するためのグループ定義４０を、事前の取り決めとして行っておく。即ちコンピュータシステム１００上で、ソート処理の実行よりも前に、対象データの形式や特性に応じたグループ定義４０を作成しておく。図４に示す本例では、グループ定義４０として、データ列４１が取り得る全データ値範囲[１〜８]を、データ値個数（Ｌ）３個程度で区切って、グループ数（Ｍ）が３つのグループ[Ｇ１，Ｇ２，Ｇ３]に分けている。即ちソート対象となるデータ列４１のレコードのデータ値において、値｛１〜３｝を第１のグループＧ１、値｛４〜６｝を第２のグループＧ２、値｛７，８｝を第３のグループＧ３とする。これらは、構成値の大小によって、Ｇ１，Ｇ２，Ｇ３の順に順序付けられて定義されている。条件としては、あるグループＧｘ内の最小値が１つ前のグループＧ（ｘ−１）内の最大値より大きく、かつ、グループＧｘ内の最大値が１つ後のグループＧ（ｘ＋１）内の最小値より小さくなるように取り決める必要がある。
【００４７】
グループ分割処理部１１２におけるグループ単位への分割処理では、データ列４１の各データ値を、グループ定義４０に従い、グループ[Ｇ１，Ｇ２，Ｇ３]に対応した、グループ単位配列（４０６〜４０８）に振り分けする。グループＧ１に含まれるデータ値に対してはＧ１配列４０１へ、といったように、メモリ１０２上に必要な配列が確保されて処理される。
【００４８】
なお、本ソート処理方法を実装しているソート処理プログラム１１０では、図５のフローのＳ５０２とＳ５０３に示すように、グループ定義４０の各グループへのデータ列１１の各データ値の振り分け判定及び振り分け処理のための所定のアルゴリズムが組み込まれる。このアルゴリズムは、例えば、グループ定義４０に対応して予め準備した、データ値ごとのインデックステーブルを参照して各データ値をグループ単位へ振り分ける方法（従来技術）等を用いる。
【００４９】
ソート動作を説明する。まず、グループ化処理として、図４のデータ列４１が、レコード読み込みにより、各グループ単位配列（４０６〜４０８）へと振り分けされる。図５のＳ５０１のレコード読み込み処理により、最初に、データ列４１におけるレコードＮｏ＝０のデータ値｛３｝が読み込まれる。Ｓ５０２とＳ５０３において、読み込まれたレコード値｛３｝が、Ｇ１〜Ｇ３のどのグループに属するかが判定される。この判定の結果、Ｓ５０２で、値｛３｝はＧ１に属すると判断され、Ｓ５０４により、Ｇ１配列４０１の末尾に、読み込まれた値｛３｝が追加される。なお実際には新たにＧ１配列４０１が作成される。Ｓ５０７では、次に続くレコードが存在するので、Ｓ５０１〜Ｓ５０６の処理をループする。
【００５０】
次に、Ｓ５０１で、レコードＮｏ＝１のデータ値｛６｝が読み込まれ、Ｓ５０２で、入力値｛６｝はＧ２に属すると判断され、Ｓ５０５により、Ｇ２配列４０２に値｛６｝が追加される。次に、Ｓ５０１で、レコードＮｏ＝２のデータ値｛８｝が読み込まれ、Ｓ５０３及びＳ５０６で、入力値｛８｝はＧ３に属すると判断され、Ｇ３配列４０３の末尾に値｛８｝が追加される。以下同様に、レコードＮｏ＝３〜７について同様の処理を繰り返し、データ列４１の各レコードのデータ値が、各グループ用の配列（４０６〜４０８）に振り分けられる。結果、Ｇ１配列４０７は[３，１，２]となり、Ｇ２配列４０８は[６，４，５]となり、Ｇ３配列４０６は[８，７]となる。
【００５１】
次に、Ｓ５０７で次に続くレコードが存在しないので、Ｓ５０８で、グループ単位配列（４０６〜４０８）について、それぞれ並べ替え、即ち個別のソート処理（ソート＃１〜ソート＃３）を実行する。この際のソート処理アルゴリズムは、既存のものを使用可能である。
【００５２】
グループ単位配列（４０６〜４０８）の各ソート処理（Ｓ５０８）により、ソート済みグループ単位配列（４０９〜４１１）が得られる。即ち、Ｇ１配列４１０は[１，２，３]となり、Ｇ２配列４１１は[４，５，６]となり、Ｇ３配列４０９は[７，８]となる。
【００５３】
最後に、Ｓ５０９の処理により、３つのソート済みグループ単位配列（４０９〜４１１）を、グループ順（Ｇ１−Ｇ２−Ｇ３）に結合する。なお、グループ単位データ列の結合処理は、広い意味ではマージ処理と言えるが、狭い意味では単なる結合であり、その処理負荷は小さい。最終的に、元のデータ列４１を正確に昇順に並べ替えたものに相当するデータ列４２（ソート結果データ列配列：Ａ２）を得ることができる。
【００５４】
前記グループ定義４０及びグループ化について補足する。前記図３では、グループ定義４０として、データ列４１に対応した全範囲[１〜８]に対し、データ値個数（Ｌ）３個程度で区切って３つ（Ｍ）のグループ[Ｇ１，Ｇ２，Ｇ３]を定義している。グループ定義４０におけるグループ数（Ｍ）、グループを構成するデータ値個数（Ｌ）などの内容（変数）について変動させても構わない。実際の処理においては、Ｍ、Ｌなどについては任意に決めてよい。即ち、処理対象データの実データレコード数や実データサイズなどをもとに、処理性能などの点を考慮して適度となるように取り決める。例えば、個別のソート処理に対応して適度なサイズのデータ値個数（Ｌ）で区切る。グループ単位の個別のソート処理は、Ｌに対して高速となるものを選択すれば望ましい。
【００５５】
例えば、本ソート処理実行時に、データ列４１の値の取り得る全範囲が[１〜１０００]の場合に、Ｌ＝１００で区切ってＭ＝１０個のグループ[Ｇ１〜Ｇ１０]とする。また例えば、データ列４１のデータ値が英文字列である場合に、文字列先頭文字が｛ａ〜ｅ｝ならばＧ１、｛ｆ〜ｋ｝ならばＧ２、｛ｌ〜ｐ｝ならばＧ３といったように、予め適切に取り決めておけばよい。その他、対象データに応じて適宜、グループ定義４０を変更したり使い分けたりしても構わない。
【００５６】
以上のように、本ソート処理方法では、グループ順に分割されたデータ列を結合するのみで、元のデータ列がソートされた結果を得ることが可能なグループを定義している。そのため、グループ単位データ列に分割して個別ソートした結果をグループ順に結合することで、図７に示すような従来のマージ処理及びその値比較処理を省略することができる。従って、特に値比較処理を要さない分、総合的なソート処理性能の向上が期待できる。
【００５７】
図７に図６のマージソート処理の一部処理であるマージ処理を示しているが、このマージ処理は、マージ対象データ列の長さが大きくなる程、値の比較回数が増加する。この処理時間は、データ列中のデータ値個数（レコード数）をＮとした場合、Ｎ×log(Ｎ)に比例することが一般的に知られており、Ｎが多くなる程その処理性能は劣化する。
【００５８】
一方、本実施の形態におけるソート処理時間（グループ単位のソート処理を順次に実行する場合）は、ソート対象データ列のデータ値個数Ｎをグループ数Ｍで分割した場合に、Ｍ×(Ｎ/Ｍ)×log(Ｎ/Ｍ)＝Ｎ×log(Ｎ/Ｍ)となる。データ値個数Ｎが多くなるほど、従来処理に比較して処理性能を大きく改善することができる。なおここで考慮しなければならない点として、従来のマージソート処理と、本実施の形態の処理とにおける、ソート対象データを分割するための処理時間があるが、従来処理（ソート済み列の抽出処理）では単純にデータ列中の各データ値の次データ値との大小比較回数(Ｎ−１)に比例する。しかし本実施の形態における処理では、ソート対象データ列中の各データ値をグループ化（振り分け）するために、前記インデックステーブルを用いる方法などのいくつかの方法／手段が考えられる。そのため、従来のマージソート処理と単純には比較できないが、本来のソート処理に要する時間の差に大きな影響を与えることは無い。
【００５９】
従来のマージソート処理方法と本ソート処理方法との効果を比較する。前記Ｎ×log(Ｎ)とＮ×log(Ｎ/Ｍ)とを具体的な値で比較する。データ値個数Ｎのレコードから成る元のデータ列を、Ｍ＝１０個のグループ[Ｇ１〜Ｇ１０]で分割した場合、処理時間は以下のように見積もることができる。まずＮ＝100の場合、Ｎ×log(Ｎ)＝100×6.64＝664であり、Ｎ×log(Ｎ/Ｍ)＝100×3.32＝332である。これらを比較すると、332/664＝1/2であり、従来の約半分の処理時間で済むことが期待できる。また、Ｎ＝1000の場合、Ｎ×log(Ｎ)＝1000×9.97＝9970であり、Ｎ×log(Ｎ/Ｍ)＝1000×6.64=6640である。比較すると、6640/9970≒2/3である。また、Ｎ=10000の場合、Ｎ×log(Ｎ)＝10000×13.29＝132900であり、Ｎ×log(Ｎ/Ｍ)＝10000×9.97＝99700である。比較すると、99700/132900＝0.75≒3/4である。
【００６０】
以上から、本実施の形態によるソート処理方法及びそのソート処理プログラム１１０でのソート処理は、従来のマージソート処理と比較して、処理時間を短縮することが可能である。
【００６１】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【産業上の利用可能性】
【００６２】
本発明は、ソート処理を用いる情報処理システム全般に利用可能であり、特にデータベース検索処理システムなどにも有効である。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施の形態のソート処理方法の原理を示す説明図である。
【図２】本発明の一実施の形態のソート処理方法に従った処理を実行するコンピュータシステムの構成を示す図である。
【図３】本発明の一実施の形態のソート処理方法に従った処理を実行するコンピュータシステムにおける、ソート対象データ列を含んだデータベースの構成例を示す図である。
【図４】本発明の一実施の形態のソート処理方法におけるデータ列のソート処理例を示す説明図である。
【図５】本発明の一実施の形態のソート処理方法におけるデータ列のソート処理例を示すフローチャートである。
【図６】従来のマージソート方法の処理例を示す説明図である。
【図７】従来のマージソート方法で用いる一般的な併合（マージ）処理の説明図であり、(ａ)はマージ対象データ列、(ｂ)はマージ結果データ列、(ｃ)はマージ処理のフローチャートを示す。
【符号の説明】
【００６４】
１０，４０…グループ定義、１１…データ列（ソート対象データ列）、１２…データ列（ソート結果データ列）、２１〜２３…グループ単位データ列、２４〜２６…ソート済みグループ単位データ列、４１…配列（ソート対象データ列配列）、４２…配列（ソート結果データ列配列）、１００…コンピュータシステム、１０１…処理装置（ＣＰＵ）、１０２…メモリ、１０３…記憶装置、１０４…入力データ、１０５…結果データ、１０６…入力部、１０７…出力部、１０８…表示部、１０９…通信Ｉ/Ｆ部、１１０…ソート処理プログラム、１１１…データ読込処理部、１１２…グループ分割処理部、１１３…ソート処理部、１２０…ＯＳ、１３０…ワークエリア、４０１〜４１１…配列、６００…マージソート対象データ列、６０１〜６０４…データ列、６０５…マージソート結果データ列。
【特許請求の範囲】
【請求項１】
コンピュータ上において、ソート対象となる第１のデータ列の全体をソートするソート処理方法であって、
前記第１のデータ列を構成するデータ値が取り得る全範囲における任意に区切られ順序付けを持つ複数のグループをもとに、
前記コンピュータが、前記第１のデータ列を前記グループ単位に分割することにより複数の第２のデータ列を得る第１の処理ステップと、
前記コンピュータが、前記複数の第２のデータ列に対してそれぞれソート処理を行って、ソート処理済みの、複数の第３のデータ列を得る第２の処理ステップと、
前記コンピュータが、前記複数の第３のデータ列を前記複数のグループの順序付けに従って順番に結合した第４のデータ列をソート結果として得る第３の処理ステップとを有することを特徴とするソート処理方法。
【請求項２】
請求項１記載のソート処理方法において、
前記コンピュータが、前記第１のデータ列に対応した前記複数のグループの定義を作成する処理ステップを有し、
前記複数のグループは、前記第１のデータ列を構成するデータ値が取り得る値の全範囲を、任意のデータ値個数で区切ってなることを特徴とするソート処理方法。
【請求項３】
請求項１記載のソート処理方法において、
前記コンピュータが、前記第１のデータ列に対応した第１の配列と、前記グループ単位の複数の第２のデータ列に対応した複数の第２の配列とを使用して、
前記第１の処理ステップでは、前記第１の配列の先頭のデータ値から末尾のデータ値までを順に、前記複数の第２の配列へ振り分けし、
前記第２の処理ステップでは、前記複数の第２の配列を、個別にソート処理し、
前記第３の処理ステップでは、前記個別にソート処理済みの複数の第２の配列を、前記複数のグループの順序付けに従ってマージ処理無しで結合することにより第３の配列をソート結果として得ることを特徴とするソート処理方法。
【請求項４】
ソート対象となる第１のデータ列の全体をソートするソート処理方法に従った処理をコンピュータに実行させるプログラムであって、
前記第１のデータ列を構成するデータ値が取り得る全範囲における任意に区切られ順序付けを持つ複数のグループをもとに、
前記第１のデータ列を前記グループ単位に分割することにより複数の第２のデータ列を得る第１の処理と、
前記複数の第２のデータ列に対してそれぞれソート処理を行って、ソート処理済みの、複数の第３のデータ列を得る第２の処理と、
前記複数の第３のデータ列を前記複数のグループの順序付けに従って順番に結合した第４のデータ列をソート結果として得る第３の処理とを前記コンピュータに実行させることを特徴とするプログラム。
【請求項１】
コンピュータ上において、ソート対象となる第１のデータ列の全体をソートするソート処理方法であって、
前記第１のデータ列を構成するデータ値が取り得る全範囲における任意に区切られ順序付けを持つ複数のグループをもとに、
前記コンピュータが、前記第１のデータ列を前記グループ単位に分割することにより複数の第２のデータ列を得る第１の処理ステップと、
前記コンピュータが、前記複数の第２のデータ列に対してそれぞれソート処理を行って、ソート処理済みの、複数の第３のデータ列を得る第２の処理ステップと、
前記コンピュータが、前記複数の第３のデータ列を前記複数のグループの順序付けに従って順番に結合した第４のデータ列をソート結果として得る第３の処理ステップとを有することを特徴とするソート処理方法。
【請求項２】
請求項１記載のソート処理方法において、
前記コンピュータが、前記第１のデータ列に対応した前記複数のグループの定義を作成する処理ステップを有し、
前記複数のグループは、前記第１のデータ列を構成するデータ値が取り得る値の全範囲を、任意のデータ値個数で区切ってなることを特徴とするソート処理方法。
【請求項３】
請求項１記載のソート処理方法において、
前記コンピュータが、前記第１のデータ列に対応した第１の配列と、前記グループ単位の複数の第２のデータ列に対応した複数の第２の配列とを使用して、
前記第１の処理ステップでは、前記第１の配列の先頭のデータ値から末尾のデータ値までを順に、前記複数の第２の配列へ振り分けし、
前記第２の処理ステップでは、前記複数の第２の配列を、個別にソート処理し、
前記第３の処理ステップでは、前記個別にソート処理済みの複数の第２の配列を、前記複数のグループの順序付けに従ってマージ処理無しで結合することにより第３の配列をソート結果として得ることを特徴とするソート処理方法。
【請求項４】
ソート対象となる第１のデータ列の全体をソートするソート処理方法に従った処理をコンピュータに実行させるプログラムであって、
前記第１のデータ列を構成するデータ値が取り得る全範囲における任意に区切られ順序付けを持つ複数のグループをもとに、
前記第１のデータ列を前記グループ単位に分割することにより複数の第２のデータ列を得る第１の処理と、
前記複数の第２のデータ列に対してそれぞれソート処理を行って、ソート処理済みの、複数の第３のデータ列を得る第２の処理と、
前記複数の第３のデータ列を前記複数のグループの順序付けに従って順番に結合した第４のデータ列をソート結果として得る第３の処理とを前記コンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００７−１３３５７６（Ｐ２００７−１３３５７６Ａ）
【公開日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願番号】特願２００５−３２４９２２（Ｐ２００５−３２４９２２）
【出願日】平成１７年１１月９日（２００５．１１．９）
【出願人】（０００２３３２９５）日立情報通信エンジニアリング株式会社 (195)
【公開日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願日】平成１７年１１月９日（２００５．１１．９）
【出願人】（０００２３３２９５）日立情報通信エンジニアリング株式会社 (195)
[ Back to top ]