分治法，顾名思义就是对复杂的，难以直接求解的问题采用“分而治之”的方法加以解决。分治法的三个步骤。
很多经典算法都使用了分治法的思想，如：
二分搜索法（Binary Search）归并排序（Merge Sort）快速排序（Quicksort ）汉诺塔问题（Hanoi）Strassen算法（Strassen’s Algorithm）下面我们以归并排序来说明。
public static int[] mergeSort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
return arr;
}
private static void merge(int[] arr, 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 (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = arr[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = arr[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
arr[k2 + low] = temp[k2];
}
}
例子中将待排序的数组每次一分为二，然后递归分割直到不能分割为止（把单个元素当做一个有序数组），merge方法将两个有序序列合并为一个有序序列。采用双指针遍历两个有序数组。即左指针（i）指向每次分割后左边数组第一个元素，右指针（j）指向每次分割后右边数组第一个元素。然后依次从小到大填充到temp数组中。
下面用两张图来加深理解
根据分治思想结合归并排序例子我们可以总结下采用分治法要解决的问题需要具备的特征有
问题可分解为若干规模较小的相同类型的子问题。子问题规模缩小到一定程度后很容易的求解。利用子问题的解可求解原问题的解。各个子问题是相互独立的，子问题直接不包含公共的子问题。