Merge sort is a recursive divide-and-conquer algorithm that divide the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]; i += 1
else:
arr[k] = R[j]; j += 1
k += 1
while i < len(L):
arr[k] = L[i]; i += 1; k += 1
while j < len(R):
arr[k] = R[j]; j += 1; k += 1function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [], i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return result.concat(left.slice(i)).concat(right.slice(j));
}