Merge Sort

Approach #1

public void mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
mergeSort(a, low, mid);
// 右边
mergeSort(a, mid + 1, high);
// 左右归并
merge(a, low, mid, high);
System.out.println(Arrays.toString(a));
}
}
public void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low; // 左指针
int j = mid + 1; // 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
a[k2 + low] = temp[k2];
}
}

Approach #2

class Solution {
public ArrayList<Integer> mergeSort(ArrayList<Integer> array) {
int size = array.size();
if (size < 2) {
return array;
}
int middle = size / 2;
List<Integer> left = array.subList(0, middle);
List<Integer> right = array.subList(middle, size);
ArrayList<Integer> leftArray = new ArrayList<Integer>();
leftArray.addAll(left);
ArrayList<Integer> rightArray = new ArrayList<Integer>();
rightArray.addAll(right);
return merge(mergeSort(leftArray), mergeSort(rightArray));
}
public ArrayList<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right) {
ArrayList<Integer> result = new ArrayList<Integer>();
while (left.size() > 0 && right.size() > 0) {
if (left.get(0) <= right.get(0)) {
result.add(left.get(0));
left.remove(0);
} else {
result.add(right.get(0));
right.remove(0);
}
}
if (left.size() > 0) {
result.addAll(left);
}
if (right.size() > 0) {
result.addAll(right);
}
return result;
}
}