void merge_sort(T *A, int l, int r){
	int m;
	if(l<r){
		m = (l+r)/2;
		// divide
		merge_sort(A,l,m);
		merge_sort(A,m+1,r);
		// l~m / m+1~r 까지는 정렬된 상태
		merge(A,l,m,r);
	}
}
T *buf
void merge(T *A, int l , int r, int m){
	int ptr,p_l, p_r;
	memcpy(buf+l, A+l, sizeof(T) *(r-l+1));
	p_l=l,p_r=r;
	ptr=l;
	while((p_l <= m) && (p_r<=r)){
		if( buf[p_l] < buf[p_r]){
			A[ptr++] = buf[p_l++];
		}else {
			A[ptr++] = buf[p_r++];
		}
	}
	while (p_l <= m)
		A[ptr++] = buffer[p_l++];
	while (p_r <= right)
		A[ptr++] = buffer[p_r++];
}
	

typedef struct{
	int key;  // org value
	int link; // init value = -1
}

// return : start of the sorted list
int rmerge(element list[], int lower, int upper){
	int m = (l+u)/2;
	if( l >= u ) return l;
	else return listmerge(list, rmerge(list, l, m), rmerge(list, m+1,r));
}

int listmerge(element list[], int f, int s){
	int start = n; 
	while(first != -1 && second != -1) {
		if(list[first].key <= list[second].key) {
			list[start].link= first; // concat
			start = first;
			first = link[first].link; // 그 다음거
		}
		else {
			list[start].link= first; // concat
			start = first;
			first = link[first].link; // 그 다음거
		}
	}
	if(first == -1) // first의 마지막 원소에 도달
		list[start].link = second;
	else
		list[start].link = first;
	return list[n].link;
}

void quick_sort(item_type *A, int left, int right) {
	int pivot;
	if (right - left > 0) {
		pivot = partition(A, left, right);
		quick_sort(A, left, pivot - 1);
		quick_sort(A, pivot + 1, right);
	}
}

int partition(item_type *A, int left, int right) {
	int i, pivot;
	pivot = left; // 그냥 맨 앞에 있는거로 잡음
	for (i = left; i < right; i++) {
		if (A[i] < A[right]) {
			SWAP(A[i], A[pivot]);
			pivot++;   //			How is the pivot element chosen in this function?
		}
	}
	SWAP(A[right], A[pivot]);
	return(pivot);
}

void quick_sort(element e, int left, int right) {
	... // linked list 구현
}

swap(a[mid] , a[r-1]);
if(a[l] < a[r-1] )
	swap(a[l] , a[r-1]); // 큰놈이 a[l]
if(a[l] < a[r])
	swap(a[l],  a[r]) ;// 큰놈이 a[l]
if(a[r-1] < a[r])
	swap(a[r-1],  a[r]) ;// 큰놈이 a[r-1]
	
=> a[l] > a[r-1] > a[r] 순서

r[0] = (rand() % (k-i+1)) + i;
r[0] = (rand() % (k-i+1)) + i;
r[0] = (rand() % (k-i+1)) + i;
issort(r,3,sizeof(int),compare_int); 
memcpy(pval, &a[r[1]*esize], esize);

// i가 시작 k가 끝 인덱스
i--; k++; //do while 을 고려한 처리

while(true){

	do{k--}while(compare(&a[k*esize], pval) > 0);
	do{i++}while(compare(&a[i*esize], pval) < 0);
	
	if( i >= k ) break; // 잘못된 위치에 있는 원소가 없다.
	else {
		swap(a[i], a[k]) // 원래는 memcpy로 해야하는데 생략
	}
}

return k;  // 파티셔닝된 pivot의 인덱스 리턴
 

if (i < k) {
    if ((j = partition(data, esize, i, k, compare)) < 0)
        return -1;

    if (qksort(data, size, esize, i, j, compare) < 0)
        return -1;

    if (qksort(data, size, esize, j + 1, k, compare) < 0)
        return -1;
}
return 0;

void bubble(T *A, int n){
	int i,j;
	loop(i, n-1){ // i는 인덱스로 사용하지 않고, iteration의 횟수를 보장하기 위해 사용된다.
		for(j = n-1; j > i; j--){
			if(A[j] < A[j-1]){
				swap(A[j], A[j-1]);
			}
		}
	}
}

func maxmin(S)
	//base case
	if sizeof(S) == 2
		return (큰놈,작은놈);
	// 아닌 경우
	else{
		divide S into S1 / S2
		max1, min1 = maxmin(S1)
		max2, min2 = maxmin(S2)
		return (max(max1, max2) , min(min1, min2))
	}

x = a | b
y = c | d

           xy
           │
    ┌──────┼──────┐
    │             │
  ac, bd        (a+b)(c+d)
   │  │             │
   └──┴── combine ──┘
        │
   xy = P₁·2ⁿ + (P₃−P₁−P₂)·2ⁿ/² + P₂