1.merge-sort.md

Merge Sort

Links

• https://hackernoon.com/programming-with-js-merge-sort-deb677b777c0
• https://en.wikipedia.org/wiki/Merge_sort

// Split the array into halves and merge them recursively 
function mergeSort (arr) {
  if (arr.length === 1) {
    // return once we hit an array with a single item
    return arr
  }

  const middle = Math.floor(arr.length / 2) // get the middle item of the array rounded down
  const left = arr.slice(0, middle) // items on the left side
  const right = arr.slice(middle) // items on the right side

  return merge(
    mergeSort(left),
    mergeSort(right)
  )
}

// compare the arrays item by item and return the concatenated result
function merge (left, right) {
  let result = []
  let indexLeft = 0
  let indexRight = 0

  while (indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] < right[indexRight]) {
      result.push(left[indexLeft])
      indexLeft++
    } else {
      result.push(right[indexRight])
      indexRight++
    }
  }

  return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight))
}

const list = [2, 5, 1, 3, 7, 2, 3, 8, 6, 3]
console.log(mergeSort(list)) // [ 1, 2, 2, 3, 3, 3, 5, 6, 7, 8 ]

<?php
declare(strict_types = 1);

function mergeSort($arr)
{
    if (count($arr) <= 1) {
        return $arr;
    }

    $middle = (int) (count($arr) / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);

    return merge(
        mergeSort($left),
        mergeSort($right)
    );
}

function merge($arr1, $arr2)
{
    $result = [];
    while (\count($arr1) || \count($arr2)) {
        if (!\count($arr1)) {
            return array_merge($result, $arr2);
        }
        if (!\count($arr2)) {
            return array_merge($result, $arr1);
        }
        if ($arr1[0] < $arr2[0]) {
            $result[] = array_shift($arr1);
        } else {
            $result[] = array_shift($arr2);
        }
    }

    return $result;
}

var_dump(mergeSort([2, 5, 1, 3, 7, 2, 3, 8, 6, 3])); // [ 1, 2, 2, 3, 3, 3, 5, 6, 7, 8 ]