Merge sort is one of the classic sorting algorithms. It divides the input array into two halves, recursively sorts each half, then merges the two sorted halves.
In this problem merge sort is used to sort an array of integers in ascending order. The exact behavior is given by the following pseudo-code:
function merge_sort(arr):
n = arr.length()
if n <= 1: