ProAnswers.org

algorithm Merge Sort

algorithm Merge Sort

void merge_sort(int list[], int first, int last){
int mid = (first + last) / 2;
if(first == last)
return;
merge_sort(list, first, mid);
merge_sort(list, mid + 1, last);
merge(list, first, mid, last);
}

void merge(int list[], int first, int mid, int last){
int m, n, i = 0, j = 0, k = first;
m = mid - first + 1;
n = last - mid;
int a[m], b[n];
while(i < m){
a[i] = list[k];
i++, k++;
}
while(j < n){
b[j] = list[k];
j++, k++;
}
i = 0, j = 0, k = first;
while(i < m && j < n){
if(a[i] < b[j]){
list[k] = a[i];
i++, k++;
}
else{
list[k] = b[j];
j++, k++;
}
}
if(i == m){
while(k <= last){
list[k] = b[j];
j++, k++;
}
}
if(j == n){
while(k <= last){
list[k] = a[i];
i++, k++;
}
}
}