알고리즘 정리-비귀속 병합 정렬

귀속은 좋은 물건으로 큰 문제를 여러 개의 작은 문제로 나눌 수 있다.작은 문제 하나하나와 작은 문제를 큰 문제로 합치는 작업만 잘 처리하면 기본적으로 완성된 것이고 프로그램은 작은 문제를 해결하는 코드를 쓰면 된다.그러나 귀환에도 결함이 있을 수 있다. 만약에 귀환 층수를 잘 제어하지 못하거나 귀환 과정에서 대량의 변수가 발생하면 창고가 넘치기 쉽다.특히 공사에서 창고가 넘치는 문제는 극력 피해야 한다.
자주 사용하는 병합 정렬은 병합 정렬 방식을 사용하여 정렬 서열을 한 층 한 층 반으로 나누어 한 층의 정렬을 완성한 후에 다시 한 층 위로 되돌려 처리하는 것이다.
사실 병합 정렬은 다음과 같은 대략적인 절차에서 비귀속 방법을 사용할 수도 있습니다.
1. 순환하여 각 구역을 구분하고 각 구역은 1부터 시작한다.
2. 인접한 두 개의 구역을 병합 정렬하는 방법에 따라 버퍼에 넣는다.
3. 버퍼에서 원래 구역의 위치로 복사하기;
4. 모든 구역이 통합될 때까지 2로 돌아가기;
5. 1로 돌아가면 세그먼트가 수조의 길이보다 클 때까지 세그먼트가 2배로 커진다.

/**
 * param
 * arr: ， len 
 *
 */
void merge_sort(int* arr, int len){

	int * buff = new int[len]; //buffer 

	// 
	for(int i = 1 ; i < len ; i *= 2){
		// 
		for(int j = 0 , k = i ; k < len ; j += 2*i, k += 2*i ){
			int buffIndex = 0 ;        //buffer  index

			// 
			for(int m = j , n = k ; ; ){
				if(arr[m] <= arr[n]){
					buff[buffIndex++] = arr[m++];

					if(m >= k){ //  copy
						while(n < k + i && n < len){
							buff[buffIndex++] = arr[n++];
						}
						break;
					}
				}else{
					buff[buffIndex++] = arr[n++];

					if(n >= k+i || n >= len){  // copy
						while(m < k ){
							buff[buffIndex++] = arr[m++];
						}
						break;
					}
				}
			}

			// buffer copy 
			for(int l = 0 ; l < 2*i && j + l < len; l++){
				arr[j+l] = buff[l];
			}
		}
	}
	delete [] buff;
}