【Java】２次元配列のソート

　２次元配列でのソートを調べていたところ、基本的に Comparator でのやり方が多かったのと、Comparator の例 だと縦方向（array[y][x] の場合）でのソートが中心なので、横方向でのソートを一般的なソートアルゴリズムでやってみようと思った。

(※) ソートの結果は Comparator の作り方による

■Comparator を用いた２次元配列のソート(縦方向)
■２次元配列のクイックソート(横方向)
■２次元配列のマージソート(横方向)
■２次元配列の挿入ソート(横方向)
■横(列)方向の逆順(降順)ソート

■Comparator を用いた２次元配列のソート(縦方向)

　はじめに、Comparator を用いた、縦方向の２次元ソートを書いておこう。こっちの方が汎用性は高いので、使い方を覚えれば、柔軟なソートができて便利だ。ソート自体は「Arrays.sort()」を使う。

●Comparator を用いた２次元配列のソート（一番単純な例）

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
    int[][] arr = {
        {5, 2},
        {1, 4},
        {3, 5},
        {4, 3},
        {2, 1}
    };

    Arrays.sort(arr, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];    //[0] をキーにソート(昇順)
            //return o2[0] - o1[0];    //[0] をキーにソート(降順)
        }
    });
}

　結果は一番上の画像(右側)のようになる。

　この例では同じ値はないが、ソートするキーが同じ値の場合、比較関数を少しいじれば、第２ソートキーを付け加えることもできる。

●Comparator を用いた２次元配列のソート（第２ソートキーを加える）

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
    int[][] arr = {
        {5, 2},
        {1, 4},
        {3, 5},
        {4, 3},
        {2, 1}
    };

    Arrays.sort(arr, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if (o1[0] == o2[0]) {
                return o2[1] - o1[1];    //第２ソートキー [1] でソート(降順)
            } else {
                return o1[0] - o2[0];    //第１ソートキー [0] でソート(昇順)
            }
        }
    });
}

　ポイントは、Comparator インターフェイス の「compare()」メソッドを Override しなくてはならないわけだが、この関数の戻値が「負の値」のとき、配列の要素は昇順になり、「正の値」のときは降順になるという点だ（要するに a < b のとき、a - b = 負の値、a > b のとき、a - b = 正の値、a == b のとき、a - b = 0 として並びを決めていると考えれば良い）。今回は int 型なので、引き算をしているが、他のオブジェクト（Integer、String 等）でも比較できるものはだいたい「Comparable インターフェイス」を持っているので、そのオブジェクトの「compareTo()」の戻値をそのまま返せば良い。


　毎回同じようなソートをするなら、Comparator を implements した比較用クラスを作ってしまえば、使い回しも可能だ。

●Comparator を用いた２次元配列のソート（比較用クラスを作る）

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
    int[][] arr = {
        {5, 2},
        {1, 4},
        {3, 5},
        {4, 3},
        {2, 1}
    };

    MyComparator comparator = new MyComparator(0);
    Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

    /** ソートキーとなる col インデクス (arr[row][col]) */
    public int sortIndex = 0;

    //コンストラクタ
    public MyComparator(int sortIndex) {
        this.sortIndex = sortIndex;
    }

    //比較関数
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[sortIndex] - o2[sortIndex];    //a<b(<c<d...) としたいとき
    }
}

　「sortIndex」は面倒なので public スコープにしてあるが、private スコープにして setter を作るのも良いだろう。

　降順（逆順）にするには、上記の比較関数（compare()）の戻値を逆にする。

●Comparator を用いた２次元配列のソートを降順(逆順)にする（比較関数のみ）

・・・(略)・・・
    //比較関数
    @Override
    public int compare(int[] o1, int[] o2) {
        return o2[sortIndex] - o1[sortIndex];    //a>b(>c>d...) としたいとき
    }
・・・(略)・・・

　また毎回書き直すのが面倒だと思ったら、とりわけ int 型などは使用頻度は高いので、メンバを付け加えた独立したクラスとして作って置くのが良い。その方が機能を追加しやすい。例えば、ソートオーダー（昇順/降順）を自由に切り替えられるようにするには、以下のようにする。

●Comparator を用いた２次元配列のソートにソートオーダー（昇順/降順）を加える

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
・・・(略)・・・
    MyComparator comparator = new MyComparator(0, false);  //降順になる
    Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

    /** ソートキーとなる col インデクス (arr[row][col]) */
    public int sortIndex = 0;

    /** 昇順フラグ (true = 昇順 / false = 降順) */
    public boolean ascend = true;

    //コンストラクタ
    public MyComparator(int sortIndex) {
        this.sortIndex = sortIndex;
    }
    public MyComparator(int sortIndex, boolean ascend) {
        this.sortIndex = sortIndex;
        this.ascend = ascend;
    }

    //比較関数
    @Override
    public int compare(int[] o1, int[] o2) {
        if (ascend) {
            return o1[sortIndex] - o2[sortIndex];    //a<b(<c<d...) としたいとき
        } else {
            return o2[sortIndex] - o1[sortIndex];    //a>b(>c>d...) としたいとき
        }
    }
}

　またこのように考えれば、同値のときの第２ソートキーを付け加えるのも簡単だ。同じようにメンバを追加して、比較関数の条件を加えれば良い。

●Comparator を用いた２次元配列のソートに第２ソートキーを加える

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
・・・(略)・・・
    MyComparator comparator = new MyComparator(1, false);  //降順になる
    comparator.sortIndex2 = 0;    //第２ソートキー
    comparator.ascend2 = false;    //降順になる
    Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

    /** ソートキーとなる col インデクス (arr[row][col]) */
    public int sortIndex = 0;

    /** 昇順フラグ (true = 昇順 / false = 降順) */
    public boolean ascend = true;

    /** ソートキー(第２キー)となる col インデクス (arr[row][col]) */
    public int sortIndex2 = 1;

    /** 昇順フラグ(第２キー) (true = 昇順 / false = 降順) */
    public boolean ascend2 = true;

    //コンストラクタ
    public MyComparator(int sortIndex) {
        this.sortIndex = sortIndex;
    }
    public MyComparator(int sortIndex, boolean ascend) {
        this.sortIndex = sortIndex;
        this.ascend = ascend;
    }

    //比較関数
    @Override
    public int compare(int[] o1, int[] o2) {
        if (o1[sortIndex] == o2[sortIndex]) {    //第１キーが等しいときは、第２キーで比較
            if (ascend2) {
                return o1[sortIndex2] - o2[sortIndex2];    //a<b(<c<d...) としたいとき
            } else {
                return o2[sortIndex2] - o1[sortIndex2];    //a>b(>c>d...) としたいとき
            }
        } else {
            if (ascend) {
                return o1[sortIndex] - o2[sortIndex];    //a<b(<c<d...) としたいとき
            } else {
                return o2[sortIndex] - o1[sortIndex];    //a>b(>c>d...) としたいとき
            }
        }
    }
}

　今回は割愛したが、第２ソートキーを加えたコンストラクタを付け加えるのも良いだろう。

　この手のインターフェイスや関数は他の言語にもあるので（Ｃ系やVB等の IComparer など）、考え方がわかれば、色々応用は効く。


－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　
■一般的なソートアルゴリズムを用いた２次元配列のソート(横方向)

　次に、横方向でのソートを一般的なソートアルゴリズムでやってみる。これは Arrays.sort() ではできないので、自作することになる。

●2次元配列のクイックソート(横方向)

/**<h1>２次元配列のクイックソート(範囲指定)</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。主に再帰用。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param first ： 範囲の開始インデクス
 * @param last ： 範囲の終了インデクス
 */
public static final void qsort(int[][] arr, final int sortIndex, final int first, final int last) {
    int i, j, k, p, tmp;

    i = first;    //前方検索インデクス
    j = last;    //後方検索インデクス
    p = (arr[sortIndex][i] + arr[sortIndex][j]) / 2;    //基準値(※オーバフロー注意)

    final int row = arr.length;

    while (true) {
        while (arr[sortIndex][i] < p) {    //基準値以上の位置まで前方検索
            i++;
        }
        while (arr[sortIndex][j] > p) {    //基準値以下の位置まで後方検索
            j--;
        }
        if (i >= j) {    //交差したら終了
            break;
        }

        //スワップ
        for (k = 0; k < row; k++) {
            tmp = arr[k][i];
            arr[k][i] = arr[k][j];
            arr[k][j] = tmp;
        }

        i++;
        j--;
    }

    //基準値より２分割して再帰呼び出し(２分割できないときは再帰停止)
    if (first < i - 1) {
        qsort(arr, sortIndex, first, i - 1);
    }
    if (j + 1 < last) {
        qsort(arr, sortIndex, j + 1, last);
    }
}

/**<h1>２次元配列のクイックソート</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。範囲は最初から最後まで。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 */
public static final void qsort(int[][] arr, final int sortIndex) {
    qsort(arr, sortIndex, 0, arr[0].length - 1);
}

→ 逆順(降順)でのクイックソート

　クイックソートのアルゴリズムは検索すればいくらでも出てくるので割愛。なお、基準値(p : Pivot) は簡略のため検索範囲の最初と最後の値を加算して２で割っているが(平均値)、Wikipedia の med3 関数のような中間値(中央値)でも良い。このピボットの値をどう取るかで効率が変わるので色々研究されているらしい。実際には元の並びにもよるのでやりやすいものを使えば良いだろう。

　また注意点としては、このクイックソートは安定ソートではないので、同値の場合は、他の行の並びは不定になる。他の行の順序も考慮に入れたいのなら、安定ソートのもので第２ソートキー比較などを入れる工夫が必要になるだろう。マージソートを２回使う手もある。連番なら問題はない。

　逆順(降順)にしたいなら、後述する Comparator を用いる方法がある。昇順/降順の切り替えのみなら、boolean 型のフラグを引数にして、比較を逆にしても良いだろう。

　それと仕様として、各行の長さが違う配列には対応してない。特に例外処理は設けてないので、必要なら「ArrayIndexOutOfBoundsException」を catch か throws するようにした方が良いだろう。

　また、開始インデクスと終了インデクスの引数を持っている方の「qsort(int[][],int,int,int)」は主に再帰用なので、直接使うことがないなら、private スコープにしても良いだろう。引数の少ない「qsort(int[][],int)」の方は初めから最後までのインデクスで、引数の多い方をオーバーロードしてる感じになっている。

　あと、これを作っているとき、２次元ということもあり、アルゴリズムによる実行速度も気になったので、他のアルゴリズムとの比較もしてみた。とはいえ、測定してみたら、今回作ったものではクイックソートが一番速かったので、とりあえず qsort を使っていれば事足りるかもしれない。結果は環境や言語仕様などにも違いはあるみたいだね。アルゴリズムはあまり工夫してないし(ただスワップを列にしただけ)、スマホや携帯の場合、再帰構造はメモリを喰うので、要素数によっても変わるだろう。だからこの辺りはあくまでも適当な目安として考えて欲しい。

●今回の実行速度の結果

要素数	実行速度
10	クイックソート＞マージソート＞挿入ソート
50	クイックソート＞挿入ソート＞マージソート
100	クイックソート＞マージソート＞挿入ソート
1000	クイックソート＞マージソート＞挿入ソート
10000	クイックソート＞マージソート＞挿入ソート
50000	クイックソート＞マージソート＞挿入ソート

※速い＞遅い

　特に挿入ソートは 50～100 くらいだとむしろ速かったが、このアルゴリズムは要素数によってかなり遅くなるので、10000以上は使わない方がいいだろう。ちなみに以下の参考はＣ＋＋での比較。

(参考) 50以下挿入ソート、5万以下マージソート、あとはクイックソート
(参考) ソート(Wikipedia)

　ちなみに、Wikipedia の「ソートアルゴリズムの一覧」の「O(n²)」のような記号は「オーダー記法(ランダウの記号)」と言って、計算時間のおおよその目安を計るのに使われる。とりあえずよく使われるものとして、

　O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²)

※O(n) ・・・ データ量が 2倍, 3倍,... のとき、計算時間が 2倍, 3倍,... になる。
※O(n²) ・・・ データ量が 2倍, 3倍,... のとき、計算時間が 4倍(2²), 9倍(3²),... になる。
※計算量小[=速い] ＜ 計算量大[=遅い]

の順に計算時間がかかると覚えて置けば良いだろう。


●2次元配列のマージソート(横方向)

/**<h1>２次元配列のマージソート</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。再帰分割と結合。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 */
public static final void msort(int[][] arr, final int sortIndex) {
    final int col = arr[0].length;
    if (col <= 1) {        //分割できなくなったら、再帰停止
        return;
    }

    //配列を２分割
    final int row = arr.length;
    final int m = col / 2;    //半分より左(半端は切捨て：5 / 2 = 2)
    final int n = col - m;    //半分より右(半端はこっち：5 - 2 = 3)
    int[][] arr1 = new int[row][m];
    int[][] arr2 = new int[row][n];
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < row; j++) {
            arr1[j][i] = arr[j][i];
            arr2[j][i] = arr[j][i + m];
        }
    }
    if (n > m) {
        for (j = 0; j < row; j++) {
            arr2[j][n - 1] = arr[j][col - 1];    //２分割のため、半端は必ず最後の１つになる
        }
    }

    //再帰分割と結合
    msort(arr1, sortIndex);    //再帰呼び出し(左半分の配列)
    msort(arr2, sortIndex);    //再帰呼び出し(右半分の配列)
    merge(arr, sortIndex, arr1, arr2);    //配列のマージ
}

/**<h1>２次元配列のマージ（マージソート用）</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。昇順にマージされる。再帰用。</p>
 * @param dst ： マージされた結果配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param arr1 ： マージする配列１
 * @param arr2 ： マージする配列２
 */
private static final void merge(int[][] dst, final int sortIndex, final int[][] arr1, final int[][] arr2) {
    final int col1 = arr1[0].length;
    final int col2 = arr2[0].length;
    final int row = arr1.length;    //通常、arr1 と arr2 の row は同じ
    int i = 0;    //arr1 用インデクス
    int j = 0;    //arr2 用インデクス
    int p = 0;    //dst 用インデクス

    //小さい方を dst に追加
    int k;
    while (i < col1 && j < col2) {
        if (arr1[sortIndex][i] <= arr2[sortIndex][j]) {
            for (k = 0; k < row; k++) {
                dst[k][p] = arr1[k][i];
            }
            i++;
            p++;
        } else {
            for (k = 0; k < row; k++) {
                dst[k][p] = arr2[k][j];
            }
            j++;
            p++;
        }
    }
    
    //まだ残ってれば dst に追加
    while (i < col1) {
        for (k = 0; k < row; k++) {
            dst[k][p] = arr1[k][i];
        }
        i++;
        p++;
    }
    while (j < col2) {
        for (k = 0; k < row; k++) {
            dst[k][p] = arr2[k][j];
        }
        j++;
        p++;
    }
}

(参考) マージソート

→ 逆順(降順)でのマージソート

●2次元配列の挿入ソート(横方向)

/**<h1>２次元配列の挿入ソート</h1>
 * <p>col 方向のソート。長さの違う配列は基本的に不可。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 */
public static final void isort(int[][] arr, final int sortIndex) {
    final int row = arr.length;
    final int col = arr[0].length;
    final int[] tmp = new int[row];
    int i, j, k, t;
    for (i = 1; i < col; i++) {
        t = arr[sortIndex][i];
        if (arr[sortIndex][i - 1] > t) {
            //列の退避
            for (k = 0; k < row; k++) {
                tmp[k] = arr[k][i];
            }

            //比較
            j = i;
            do {
                for (k = 0; k < row; k++) {
                    arr[k][j] = arr[k][j - 1];    //右へずらす
                }
                j--;
            } while (j > 0 && arr[sortIndex][j - 1] > t);

            //退避した列のストア
            for (k = 0; k < row; k++) {
                arr[k][j] = tmp[k];
            }
        }
    }
}

(参考) 挿入ソート

　まぁ、ほぼまんまなので（無理矢理に列を追加したというか(笑)）、改良できそうならやった方が良いかもしれない。

－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　
■Comparator を用いて横(列)方向の逆順(降順)ソートをしてみる

　例えば、前述のクイックソートとマージソートを逆順(降順)にしてみる。上記の MyComparator と同じ作り方で、int 型に互換性のある Integer 型で Comparator を作ってみよう。Integer(int) 型はよく使うので、独立したクラスとして作って置くのも良い。

●Integer(int) 型の比較クラス

import java.util.Comparator;

/** Integer(int) 型での比較クラス */
public class IntegerComparator implements Comparator<Integer> {

    /** 昇順フラグ (true = 昇順 / false = 降順) */
    public boolean ascend = true;

    /**<h1>デフォルトコンストラクタ</h1>
     * <p>昇順リスト用。</p>
     */
    public IntegerComparator() {
    }

    /**<h1>並び方向の指定のコンストラクタ</h1>
     * <p>比較関数を昇順または降順にする。</p>
     * @param ascend ： true = 昇順 / false = 降順
     */
    public IntegerComparator(final boolean ascend) {
        this.ascend = ascend;
    }

    //比較関数
    @Override
    public int compare(Integer o1, Integer o2) {
        if (ascend) {
            return o1.compareTo(o2);    //昇順
        } else {
            return o2.compareTo(o1);    //降順
        }
    }
}

●逆順(降順)でのクイックソート (qsort に Comparator<Integer> を加えたもの)

/**<h1>２次元配列のクイックソート(範囲指定)</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。主に再帰用。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param first ： 範囲の開始インデクス
 * @param last ： 範囲の終了インデクス
 * @param comparator ： Comparator<Integer>
 */
public static final void qsort(int[][] arr, final int sortIndex, final int first, final int last, 
    final Comparator<Integer> comparator) {
    int i, j, k, p, tmp;

    i = first;    //前方検索インデクス
    j = last;    //後方検索インデクス
    p = (arr[sortIndex][i] + arr[sortIndex][j]) / 2;    //基準値(※オーバフロー注意)

    final int row = arr.length;

    while (true) {
        while (comparator.compare(arr[sortIndex][i], p) < 0) {    //基準値以上の位置まで前方検索
            i++;
        }
        while (comparator.compare(arr[sortIndex][j], p) > 0) {    //基準値以下の位置まで後方検索
            j--;
        }
        if (i >= j) {    //交差したら終了
            break;
        }

        //スワップ
        for (k = 0; k < row; k++) {
            tmp = arr[k][i];
            arr[k][i] = arr[k][j];
            arr[k][j] = tmp;
        }

        i++;
        j--;
    }
    
    //基準値より２分割して再帰呼び出し(２分割できないときは再帰停止)
    if (first < i - 1) {
        qsort(arr, sortIndex, first, i - 1, comparator);
    }
    if (j + 1 < last) {
        qsort(arr, sortIndex, j + 1, last, comparator);
    }
}

/**<h1>２次元配列のクイックソート</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。範囲は最初から最後まで。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param comparator ： Comparator<Integer>
 */
public static final void qsort(int[][] arr, final int sortIndex, final Comparator<Integer> comparator) {
    qsort(arr, sortIndex, 0, arr[0].length - 1, comparator);
}

→ 基本的なクイックソート

●逆順(降順)でのマージソート (msort に Comparator<Integer> を加えたもの)

/**<h1>２次元配列のマージソート</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。再帰分割と結合。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param comparator ： Comparator<Integer>
 */
public static final void msort(int[][] arr, final int sortIndex, final Comparator<Integer> comparator) {
    final int col = arr[0].length;
    if (col <= 1) {        //分割できなくなったら、再帰停止
        return;
    }

    //配列を２分割
    final int row = arr.length;
    final int m = col / 2;    //半分より左(半端は切捨て：5 / 2 = 2)
    final int n = col - m;    //半分より右(半端はこっち：5 - 2 = 3)
    int[][] arr1 = new int[row][m];
    int[][] arr2 = new int[row][n];
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < row; j++) {
            arr1[j][i] = arr[j][i];
            arr2[j][i] = arr[j][i + m];
        }
    }
    if (n > m) {
        for (j = 0; j < row; j++) {
            arr2[j][n - 1] = arr[j][col - 1];    //２分割のため、半端は必ず最後の１つになる
        }
    }
    
    //再帰分割と結合
    msort(arr1, sortIndex, comparator);    //再帰呼び出し(左半分の配列)
    msort(arr2, sortIndex, comparator);    //再帰呼び出し(右半分の配列)
    merge(arr, sortIndex, arr1, arr2, comparator);    //配列のマージ
}

/**<h1>２次元配列のマージ（マージソート用）</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。昇順にマージされる。再帰用。</p>
 * @param dst ： マージされた結果配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param arr1 ： マージする配列１
 * @param arr2 ： マージする配列２
 * @param comparator ： Comparator<Integer>
 */
private static final void merge(int[][] dst, final int sortIndex, final int[][] arr1, final int[][] arr2, 
    final Comparator<Integer> comparator) {
    final int col1 = arr1[0].length;
    final int col2 = arr2[0].length;
    final int row = arr1.length;    //通常、arr1 と arr2 の row は同じ
    int i = 0;    //arr1 用インデクス
    int j = 0;    //arr2 用インデクス
    int p = 0;    //dst 用インデクス

    //小さい方を dst に追加
    int k;
    while (i < col1 && j < col2) {
        if (comparator.compare(arr1[sortIndex][i], arr2[sortIndex][j]) <= 0) {
            for (k = 0; k < row; k++) {
                dst[k][p] = arr1[k][i];
            }
            i++;
            p++;
        } else {
            for (k = 0; k < row; k++) {
                dst[k][p] = arr2[k][j];
            }
            j++;
            p++;
        }
    }
    
    //まだ残ってれば dst に追加
    while (i < col1) {
        for (k = 0; k < row; k++) {
            dst[k][p] = arr1[k][i];
        }
        i++;
        p++;
    }
    while (j < col2) {
        for (k = 0; k < row; k++) {
            dst[k][p] = arr2[k][j];
        }
        j++;
        p++;
    }
}

→ 基本的なマージソート

　内容的には、比較部分を Comparator.compare() に置き換え、再帰呼び出しの引数にも加えただけである。

　メインは、

int[][] arr = {
    {5, 1, 3, 4, 2},
    {2, 4, 5, 3, 1}
};
qsort(arr, 0, new IntegerComparator(false));    //降順
//msort(arr, 0, new IntegerComparator(false));    //降順

のような感じで良い。結果は以下の様になる。

　他のアルゴリズムでも色々やってみると良いだろう。


（関連記事）
【Java】連想配列(Map)を値でソートする
【Java】配列要素の反転(reverse)
【Java】配列, リスト(List), 連想配列(Map) の初期化

■参考にできる書籍