---
title: マージソート復習
tags: []
categories: ["Programming", "Algorithm", "Sort", "MergeSort"]
date: 2014-03-04T23:19:31Z
updated: 2014-03-04T23:19:31Z
---

復習

    import java.util.Arrays;
    import java.util.Random;
    
    public class MergeSort {
    
        public static void mergesort(int[] arr) {
            mergesort(arr, 0, arr.length);
        }
    
        static void mergesort(int[] arr, int i, int j) {
            // arrのうち、i <= x < jの区間をソートする
            if (j - i <= 1) {
                // ソート済み
                return;
            }
            int mid = i + (j - i) / 2;
            mergesort(arr, i, mid);
            mergesort(arr, mid, j);
            merge(arr, i, mid, j);
        }
    
        static void merge(int[] arr, int i, int mid, int j) {
            int size = j - i;
            int[] work = new int[size];
            System.arraycopy(arr, i, work, 0, size);
    
            int k = i;
            int p = 0;
            int q = mid - i;
    
            while (p < (mid - i) && q < size) {
                if (work[p] <= work[q]) {
                    arr[k++] = work[p++];
                } else {
                    arr[k++] = work[q++];
                }
            }
    
            while (p < (mid - i)) {
                arr[k++] = work[p++];
            }
            while (q < size) {
                arr[k++] = work[q++];
            }
        }
    
        public static void main(String[] args) {
            int[] arr = new int[100];
            Random r = new Random(System.nanoTime());
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt(100);
            }
            System.out.println(Arrays.toString(arr));
            mergesort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }