Merge Sort

1void mergeSort(int[] arr, int left, int right) {2  if (left >= right) return;  // một phần tử, xong3  int mid = (left + right) / 2;  // điểm chia4  mergeSort(arr, left, mid);  // sắp nửa trái5  mergeSort(arr, mid + 1, right);  // sắp nửa phải6  merge(arr, left, mid, right);  // trộn hai nửa7}8 9void merge(int[] arr, int left, int mid, int right) {10  int[] temp = new int[right - left + 1];  // bộ đệm tạm11  int i = left, j = mid + 1, k = 0;12  while (i <= mid && j <= right)  // so hai đầu13    temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];  // lấy số nhỏ hơn14  while (i <= mid) temp[k++] = arr[i++];  // phần còn lại15  while (j <= right)  temp[k++] = arr[j++];16  for (int x = 0; x < temp.length; x++) arr[left + x] = temp[x];  // chép trở lại17}