Time Complexity
O(n logn)
Example
#include <stdio.h>
#include <string.h>
int buf[10];
void merge(int *arr, int left, int right) {
int mid = (left + right) / 2;
int index = left;
int l = left;
int r = mid+1;
while(l <= mid && r <= right) {
if (arr[l] < arr[r]) buf[index++] = arr[l++];
else buf[index++] = arr[r++];
}
while(l <= mid) buf[index++] = arr[l++];
while(r <= right) buf[index++] = arr[r++];
memcpy(arr+left, buf+left, sizeof(int)*(right-left+1));
//for(int i=left;i<=right;i++) arr[i] = buf[i];
}
void merge_sort(int *arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid+1, right);
merge(arr, left, right);
}
}
void print(int *arr, int size) {
for(int i=0;i<size;i++) printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[10] = {3, 6, 9, 2, 4, 8, 1, 5, 7, 0};
int size = 10;
merge_sort(arr, 0, size-1);
print(arr, size);
return 0;
}