ここでは Java での挿入ソート（Insertion Sort） と マージソート（Merge Sort） の わかりやすい実装コード を提示します。
初心者でも理解しやすいようにコメント付きです。
挿入ソート（Insertion Sort）
import java.util.Arrays;
public class InsertionSortExample {
// 挿入ソートのメソッド
public static void insertionSort(int[] arr) {
int n = arr.length;
// 1番目から順に、左側の並んだ領域に挿入する
for (int i = 1; i < n; i++) {
int key = arr[i]; // 挿入する値
int j = i - 1;
// 左側の並んだ部分を右にずらして挿入場所を作る
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// key を正しい位置に挿入
arr[j + 1] = key;
}
}
// 動作確認用 main
public static void main(String[] args) {
int[] array = {5, 2, 4, 6, 1, 3};
System.out.println("元の配列: " + Arrays.toString(array));
insertionSort(array);
System.out.println("挿入ソート後: " + Arrays.toString(array));
}
}
マージソート（Merge Sort）
import java.util.Arrays;
public class MergeSortExample {
// マージソート本体（分割→マージ）
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return; // 要素1つなら終了
int mid = (left + right) / 2;
// 左半分を再帰的にソート
mergeSort(arr, left, mid);
// 右半分を再帰的にソート
mergeSort(arr, mid + 1, right);
// 左右をマージ
merge(arr, left, mid, right);
}
// 左右をマージするメソッド
private static void merge(int[] arr, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int i = left; // 左側の開始
int j = mid + 1; // 右側の開始
int k = 0; // tmp のインデックス
// 小さい方を順に tmp に入れる
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
else tmp[k++] = arr[j++];
}
// 左側に残っている場合
while (i <= mid) tmp[k++] = arr[i++];
// 右側に残っている場合
while (j <= right) tmp[k++] = arr[j++];
// tmp を元の配列にコピー
for (int t = 0; t < tmp.length; t++) {
arr[left + t] = tmp[t];
}
}
// 動作確認用 main
public static void main(String[] args) {
int[] array = {5, 2, 4, 6, 1, 3};
System.out.println("元の配列: " + Arrays.toString(array));
mergeSort(array, 0, array.length - 1);
System.out.println("マージソート後: " + Arrays.toString(array));
}
}
実行例
元の配列: [5, 2, 4, 6, 1, 3]
挿入ソート後: [1, 2, 3, 4, 5, 6]
マージソート後: [1, 2, 3, 4, 5, 6]
特徴まとめ
| ソート | 計算量 | メモリ | 安定性 | 特徴 |
|---|---|---|---|---|
| 挿入ソート | 最悪 O(n²), 最良 O(n) | 追加不要 | 安定 | 小規模・ほぼ整列済みに強い |
| マージソート | O(n log n) | 追加配列必要 | 安定 | 大規模データ向け、確実に高速 |