Suppose we have a list

1 9 7 5 4 6 8 10 3 2


and our goal is to sort the list. Merge sort’s idea is to divide the list into small segments and recombine them.

Here, we have the list sorted.

## Code#

### Java Implementation#

public class MergeSort{

public void sort(int[] nums) {
copy(nums, _sort(nums));;
}

static void copy(int[] arr1, int[] arr2) {
assert arr1.length == arr2.length: "trying to copy two arrays that do not have the same size";
for (int i = 0; i < arr1.length; i ++) {
arr1[i] = arr2[i];
}
}

static int[] merge(int[] arr1, int[] arr2) {
int l1 = arr1.length;
int l2 = arr2.length;
int[] res = new int[l1 + l2];
int i1 = 0;
int i2 = 0;
while (i1 < l1 || i2 < l2) {
if (i1 < l1 && i2 < l2) {
int v1 = arr1[i1];
int v2 = arr2[i2];
if (v1 < v2) {
res[i1 + i2] = v1;
i1 += 1;
} else {
res[i1 + i2] = v2;
i2 += 1;
}
} else if (i1 < l1) {
res[i1 + i2] = arr1[i1];
i1 += 1;
} else {
res[i1 + i2] = arr2[i2];
i2 += 1;
}
}
return res;
}

static int[] subArr(int[] arr, int begin, int end) {
int[] res = new int[end - begin];
for (int i = begin; i < end; i ++) {
res[i - begin] = arr[i];
}
return res;
}

private int[] _sort(int[] nums) {
if (nums.length <= 1) {
return nums;
} else {
int mid = nums.length / 2;
return merge(
_sort(subArr(nums, 0, mid)),
_sort(subArr(nums, mid, nums.length))
);
}
}
}



### C Implementation#

void copyArr(int arr1[], int arr2[], int length) {
for (int i = 0; i < length; i ++) {
arr1[i] = arr2[i];
}
}

int* merge(int lst1[], int len1, int lst2[], int len2) {
int idx1 = 0;
int idx2 = 0;
int *res = malloc(sizeof(int) * (len1 + len2));
while (idx1 < len1 || idx2 < len2) {
int currIdx = idx1 + idx2;
if (idx1 < len1 && idx2 < len2) {
int v1 = lst1[idx1];
int v2 = lst2[idx2];
if (v1 < v2) {
res[currIdx] = v1;
idx1 ++;
} else {
res[currIdx] = v2;
idx2 ++;
}
} else if (idx1 < len1) {
res[currIdx] = lst1[idx1];
idx1 ++;
} else {
res[currIdx] = lst2[idx2];
idx2 ++;
}
}
return res;
}

int* _mergeSort(int lst[], int length) {
if (length <= 1) {
return lst;
} else {
int mid = length / 2;
return merge(
_mergeSort(subArr(lst, 0, mid), mid),
mid,
_mergeSort(subArr(lst, mid, length), length - mid),
length - mid
);
}
}

void mergeSort(int lst[], int length) {
copyArr(
lst,
_mergeSort(lst, length),
length
);
}


### Python Implementation#

def merge_sort(lst):
if len(lst) <= 1:
return lst
else:
mid = len(lst) // 2
return merge(merge_sort(lst[0:mid]), merge_sort(lst[mid:]))

def merge(left, right):
li = 0
ri = 0
ll = len(left)
rl = len(right)
res = []
while (li < ll or ri < rl):
if (li < ll and ri < rl):
lv = left[li]
rv = right[ri]
if lv < rv:
res.append(lv)
li += 1
else:
res.append(rv)
ri += 1
elif (li < ll):
res.append(left[li])
li += 1
else:
res.append(right[ri])
ri += 1
return res


## Complexity Analysis#

Merge sort takes $O(n\log n)$ to sort the list.