归并排序是分治法思想的典型应用，我们可以把一个 N 规模的问题分解成若干个小规模的子问题，用子问题的解来求解原问题。这同时也涉及到了问题的求解顺序，在动态规划算法中有自顶向下和自底向上两种不同的求解顺序。在这里一般采用的是自底向上的求解方法，比如一个 N 长度的数组，我们可以分解成 N/2 个长度为 2 或 1 的子数组，分别对子数组排序，再进行两两相并，直到归并成原始数组。
原理：假设排序顺序为增序，数组长度为 N。将数组拆分成 N 个长度为 1 的数组。然后相邻子数组进行归并，形成若干个长度为 2 或者 1 的数组，再继续进行归并，直至长度为 N。
下面这张图展示了归并的排序的全过程：
下面这张图展示了在宏观层面上归并排序的全过程：
O(nLogn) O(nLogn) O(nLogn) O(n)
1 function mergeSort(arr) { 2 var n = 1; 3 while (n < arr.length) { 4 for (var i = 0; i < arr.length; i += n*2) { 5 var arr1 = arr.slice(i, i+n); 6 var arr2 = arr.slice(i+n, i+(n*2)); 7 var temp = []; 8 while(arr1.length != 0 || arr2.length != 0){ 9 if(arr1.length === 0){ 10 temp.push(arr2.shift()); 11 continue; 12 } 13 if(arr2.length === 0){ 14 temp.push(arr1.shift()); 15 continue; 16 } 17 if(arr1[0] < arr2[0]){ 18 temp.push(arr1.shift()); 19 }else{ 20 temp.push(arr2.shift()); 21 } 22 } 23 arr.splice(i, n*2, ...temp); 24 } 25 n = n * 2; 26 } 27 } 六、快速排序
快速排序同样也使用了分治法的思想，在实际运用中使用的最多的就是快速排序。快速排序的核心思想是运用递归法，在每轮排序时指定一个基数，将基数移动到正确的位置上，然后再把基数的左右两边拆分出来，并分别进行相同的排序处理，直到其子数组长度为 1。其采用的是自顶向下的处理法。
原理：在每一轮排序中取一个基数 k ， 设 i 和 j 分别为数组的最左端和最右端，i 坐标从起始点向 k 点遍历，若找到一个比 k 大的元素，则停下来等待 j 的遍历。 j 坐标从起始点向 k 点遍历，若找到一个比 k 小的元素，则 i 和 j 坐标的元素互相交换。若有一端提前到达了 k 点，则等待满足条件后与另一端坐标交换。当 i 和 j 碰撞时，则为分治点，此时 i 和 j 相碰撞的坐标元素便是它的最终位置，以碰撞点为中心将数组拆分成两段，并进行相同的递归处理。当 i >= j 时，则为回退点。
下面给出一张维基百科上的图，展示了一轮快速排序的过程：
下面这张图展示了一段快速排序的全过程：