public void sort() {
    for (int i = 0; i < arr.length; i++) {

        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
            }
        }
    }
}

public class MergeSorter {

    public static void main(String[] args) {
        MergeSorter mergeSorter = new MergeSorter(new int[]{3, 1, 4});
        mergeSorter.sort();
        System.out.println(Arrays.toString(mergeSorter.getArr()));
    }

    private final int[] arr;

    public MergeSorter(int[] arr) {
        this.arr = arr;
    }

    public int[] getArr() {
        return arr;
    }

    public void sort() {
        doSort(0, arr.length - 1);
    }

    private void doSort(int left, int right) {
        if (left == right) {
            return;
        }
        doSort(left, (left + right) / 2);
        doSort((left + right) / 2 + 1, right);
        merge(left, (left + right) / 2, right);
    }

    private void merge(int left, int middle, int right) {
        // 两个元素
        if (right - left == 1 && arr[left] > arr[right]) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            return;
        }

        int[] merged = new int[right - left + 1];
        // merged 数组的指针
        int mergedPoint = 0;
        int leftPoint = 0; // left 指针
        int rightPoint = middle + 1; // right 指针

        while (leftPoint <= middle && rightPoint <= right) {
            int value;
            if (arr[leftPoint] <= arr[rightPoint]) {
                value = arr[leftPoint++];
            } else {
                value = arr[rightPoint++];
            }
            merged[mergedPoint++] = value;
        }
        while (leftPoint <= middle) {
            merged[mergedPoint++] = arr[leftPoint++];
        }
        while (rightPoint <= right) {
            merged[mergedPoint++] = arr[rightPoint++];
        }
        System.arraycopy(merged, 0, arr, left, merged.length);
    }
}