The list is repeatedly divided into smaller and smaller halves until each piece contains only one or zero elements. Once the list is divided, the algorithm starts merging the small pieces back together. During merging, elements are compared and placed in the correct order within the combined list.
def merge(a, b):
c = []
i = 0
j = 0
while (i < len(a) and j < len(b)):
if a[i] <= b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
return c + a[i:] + b[j:]
def sort(ls):
if len(ls) <= 1:
return ls
middle = len(ls) // 2
left = ls[0:middle]
right = ls[middle:]
return merge(sort(left), sort(right))
ls = [1, 2, 3, 4, 3, 3, 3, 8, 9]
print(sort(ls))
function merge(a, b) {
const c = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) {
c.push(a[i]);
i++;
} else {
c.push(b[j]);
j++;
}
}
return [...c, ...a.slice(i), ...b.slice(j)];
}
function sort(list) {
if (list.length <= 1) {
return list;
}
const middle = Math.round(list.length / 2);
const left = list.slice(0, middle);
const right = list.slice(middle);
return merge(sort(left), sort(right));
}
const list = [1, 2, 3, 4, 3, 3, 3, 8, 9];
console.log(sort(list));