Merge Sort

Core idea

Merge Sort follows the divide-and-conquer pattern: split the problem into smaller parts, solve them, then combine the results.

It repeatedly cuts the array into halves until single-element arrays remain, then merges them back while preserving order.

It guarantees O(n log n) performance and is especially important for understanding recursion and stable sorting.

// Делим массив на 2 части пополам,
// рекурсивно применяем деление пополам и слияние для обеих частей
// O(n*log(n))

function mergeSort (arr) {
 if (arr.length <= 1) {
   return arr;
 }

 const mid = Math.floor(arr.length / 2);
 const left = arr.slice(0 , mid);
 const right = arr.slice(mid , arr.length);

 const sortedLeft = mergeSort(left);
 const sortedRight = mergeSort(right);

 return merge(sortedLeft, sortedRight);
}

function merge(left , right) {
 const result = [];
 let i = 0
 let j = 0;

 while (i < left.length && j < right.length) {
   if (left[i] < right[j]) {
     result.push(left[i]);
     i++;
   } else {
     result.push(right[j]);
     j++;
   }
 }

 while (i < left.length) result.push(left[i++]);
 while (j < right.length) result.push(right[j++]);
 return result;
}