Merge Sort Algorithm: Explanation and Implementation in PHP and JavaScript

Merge sort is a divide-and-conquer sorting algorithm that was invented by John von Neumann in 1945. It is a stable, comparison-based algorithm that divides an unsorted array into two halves, sorts each half, and then merges the sorted halves back together. Merge sort has a time complexity of O(n*log(n)), which makes it an efficient sorting algorithm for large data sets.

How Merge Sort Works

Merge sort is a recursive algorithm that works by dividing an unsorted array into two halves, sorting each half, and then merging the sorted halves back together. The process is repeated until the entire array is sorted.

Here are the steps to perform Merge sort on an array:

1. Divide the unsorted array into two halves, a left and a right half.
2. Recursively sort the left half of the array until it is only one element.
3. Recursively sort the right half of the array until it is only one element.
4. Merge the two sorted halves back together.

The merge step is where the magic happens. To merge two sorted arrays, we need to compare the first element of each array and add the smallest element to a new array. We continue this process until we have merged all elements from both arrays into the new, sorted array.

Here is an example implementation of Merge sort in PHP:

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

  $mid = floor(count($arr) / 2);
  $left = array_slice($arr, 0, $mid);
  $right = array_slice($arr, $mid);

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

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

  while ($i < count($left) && $j < count($right)) {
    if ($left[$i] < $right[$j]) {
      array_push($result, $left[$i]);
      $i++;
    } else {
      array_push($result, $right[$j]);
      $j++;
    }
  }

  return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}

The PHP implementation is similar to the JavaScript implementation, but uses PHP-specific syntax. The mergeSort function and merge function are identical to the JavaScript implementation.

To use the mergeSort function on an array, you simply call it with the array as an argument. For example:

$unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4];
$sortedArray = mergeSort($unsortedArray);
print_r($sortedArray);

This will output [1, 2, 3, 4, 5, 6, 7, 8].

And here is an example implementation of Merge sort in JavaScript:

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);

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

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++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

The mergeSort function first checks if the input array has one or zero elements. If so, it immediately returns the array. If the array has more than one element, the function calculates the midpoint and splits the array into two sub-arrays using the slice method.

The merge function takes two sorted arrays and combines them into a single sorted array. It first creates an empty array to hold the sorted elements. Then, it iterates over the two arrays, comparing the elements and pushing the smaller one into the result array. After one of the arrays is exhausted, it concatenates the remaining elements from the other array onto the end of the result array.

To use the mergeSort function on an array, you simply call it with the array as an argument. For example:

const unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4];
const sortedArray = mergeSort(unsortedArray);
console.log(sortedArray);

This will output [1, 2, 3, 4, 5, 6, 7, 8].

Conclusion

Merge sort is a popular and efficient sorting algorithm that is used in many programming languages and applications. It is a recursive divide-and-conquer algorithm that has an average time complexity of O(n*log(n)). In this blog post, we have shown you how to implement Merge sort in PHP and JavaScript, along with examples. By understanding the Merge sort algorithm, you can become a better programmer and write more efficient code.