求中点：mid=L+(R-L)>>1
递归
在范围内求最大值：
递归行为时间复杂度估算：master公式
归并排序
归并排序：将数组分成两部分，分别对两部分进行排序，将排好序的两部分利用双指针合并成一个数组（需要一个外部空间），最后将外部空间的数组拷贝到原数组中。对每部分的排序采用递归的方式进行。
代码实现：
public class MergeTest { public static void main(String[] args) { int[] arr={2,3,5,1,7,4}; //测试 process(arr,0,arr.length-1); for (int i=0;i<arr.length;i++){ System.out.println(arr[i]); } } public static void process(int[] arr,int L,int R){ if(L==R){ return; } int mid=L+((R-L)>>1); //异或运算求中点 //递归调用 process(arr, L, mid); process(arr, mid+1, R); merge(arr,L,mid,R); } //利用辅助空间进行排序操作 public static void merge(int[] arr,int L,int M,int R){ //定义一个辅助空间用来存放merge后的数组 int[] help=new int[R-L+1]; int i=0,p1=L,p2=M+1; //都不越界 while (p1<=M && p2<=R){ //双指针，如果左侧小于等于右侧，就把左侧数据放入辅助空间中，反之亦然 help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++]; } //左侧未越界，说明右侧越界了,则把左侧剩余的数据直接放到辅助空间 while (p1<=M){ help[i++]=arr[p1++]; } //同理，两个while只会执行一个 while (p2<=R){ help[i++]=arr[p2++]; } //从L开始 for (int j=0;j< help.length;j++){ arr[L+j]=help[j]; } } }
合并有序数组
题目描述：
题解：
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p1=0,p2=0; int res[m+n]; int cur; while(p1<m || p2<n){ if(p1==m){ cur=nums2[p2++]; }else if(p2==n){ cur=nums1[p1++]; }else if(nums1[p1]<nums2[p2]){ cur=nums1[p1++]; }else{ cur=nums2[p2++]; } res[p1+p2-1]=cur; } for(int i =0;i!=m+n;i++){ nums1[i]=res[i]; } } };
