Sorting is one of the most important tasks in programming, and as you explore different algorithms, you eventually come across Merge Sort. This algorithm is well known for its efficiency and reliability, especially when dealing with large datasets. Merge Sort follows a divide-and-conquer approach, meaning it breaks the problem into smaller parts, solves each part, and then joins them back together. This makes it different from simpler algorithms like Bubble Sort or Insertion Sort, which sort the list directly through repeated comparisons.
with hands-on learning.
get the skills and confidence to land your next move.
The beauty of Merge Sort lies in its structure. Even though the idea sounds advanced, the process is actually very friendly for beginners once you understand how the splitting and merging work. Because it always divides the array into halves, it provides consistent performance, which is why it is often used in real-world applications and backend systems. In this article, we explore multiple PHP programs that show different ways of implementing Merge Sort, helping you grasp the logic step by step.
Program 1: Basic Recursive Merge Sort
This first program introduces the classic recursive approach to Merge Sort. It divides the array into two halves, sorts each half, and then merges the results to form a complete sorted list.
<?php
function mergeSort($array) {
if (count($array) <= 1) {
return $array;
}
$mid = floor(count($array) / 2);
$left = mergeSort(array_slice($array, 0, $mid));
$right = mergeSort(array_slice($array, $mid));
return merge($left, $right);
}
function merge($left, $right) {
$result = [];
$i = 0;
$j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$result[] = $left[$i];
$i++;
} else {
$result[] = $right[$j];
$j++;
}
}
while ($i < count($left)) {
$result[] = $left[$i];
$i++;
}
while ($j < count($right)) {
$result[] = $right[$j];
$j++;
}
return $result;
}
$data = [38, 27, 43, 3, 9, 82, 10];
$sorted = mergeSort($data);
print_r($sorted);
?>This version helps beginners visualize how the list keeps getting smaller until each piece contains just one element. Once that happens, merging begins, gradually building the final sorted array. It is a clean and classic example that truly represents how Merge Sort works behind the scenes.
Program 2: Merge Sort With Debug Output
This version adds simple print statements to show what is happening inside the algorithm. It helps beginners watch the splitting and merging stages clearly.
<?php
function mergeSortDebug($array, $level = 0) {
echo str_repeat("-", $level) . " Splitting: ";
print_r($array);
if (count($array) <= 1) {
return $array;
}
$mid = intdiv(count($array), 2);
$left = mergeSortDebug(array_slice($array, 0, $mid), $level + 1);
$right = mergeSortDebug(array_slice($array, $mid), $level + 1);
$merged = mergeDebug($left, $right, $level);
echo str_repeat("-", $level) . " Merged: ";
print_r($merged);
return $merged;
}
function mergeDebug($left, $right, $level) {
$merged = [];
while (!empty($left) && !empty($right)) {
if ($left[0] <= $right[0]) {
$merged[] = array_shift($left);
} else {
$merged[] = array_shift($right);
}
}
return array_merge($merged, $left, $right);
}
$data = [12, 11, 13, 5, 6, 7];
$result = mergeSortDebug($data);
?>By printing the steps, you see how the algorithm travels deeper into smaller arrays and then returns upward as it merges them back. This kind of tracing makes Merge Sort less mysterious and more approachable, especially for learners who want to visualize the flow instead of only reading theory.
Program 3: Merge Sort for Strings
Merge Sort can handle more than numbers. It works perfectly with strings as well, sorting them alphabetically. This version shows how the algorithm behaves when the array contains words.
<?php
function mergeSortStrings($array) {
if (count($array) <= 1) {
return $array;
}
$mid = floor(count($array) / 2);
$left = mergeSortStrings(array_slice($array, 0, $mid));
$right = mergeSortStrings(array_slice($array, $mid));
return mergeStrings($left, $right);
}
function mergeStrings($left, $right) {
$result = [];
while (!empty($left) && !empty($right)) {
if (strcmp($left[0], $right[0]) < 0) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
return array_merge($result, $left, $right);
}
$data = ["Mango", "Apple", "Banana", "Grape", "Cherry"];
$sorted = mergeSortStrings($data);
print_r($sorted);
?>This example demonstrates how flexible Merge Sort truly is. By switching to string comparison, it gracefully handles alphabetical sorting in the same structured way, making it a great option for text data.
Program 4: Merge Sort in Descending Order
Sometimes sorting from highest to lowest is required. This version reverses the comparison and produces a descending list using the same techniques as the original version.
<?php
function mergeSortDescending($array) {
if (count($array) <= 1) {
return $array;
}
$mid = floor(count($array) / 2);
$left = mergeSortDescending(array_slice($array, 0, $mid));
$right = mergeSortDescending(array_slice($array, $mid));
return mergeDescending($left, $right);
}
function mergeDescending($left, $right) {
$result = [];
while (!empty($left) && !empty($right)) {
if ($left[0] > $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
return array_merge($result, $left, $right);
}
$data = [4, 1, 9, 7, 2];
$sorted = mergeSortDescending($data);
print_r($sorted);
?>Changing the comparison direction gives you complete control over how the final output looks. It is a simple adjustment, yet it produces a very different outcome.
Program 5: Merge Sort Using a Custom Comparator
There are times when you need to sort more complex data, such as objects or associative arrays. This version allows you to define your own comparison logic.
<?php
function mergeSortCustom($array, $compare) {
if (count($array) <= 1) {
return $array;
}
$mid = floor(count($array) / 2);
$left = mergeSortCustom(array_slice($array, 0, $mid), $compare);
$right = mergeSortCustom(array_slice($array, $mid), $compare);
return mergeCustom($left, $right, $compare);
}
function mergeCustom($left, $right, $compare) {
$result = [];
while (!empty($left) && !empty($right)) {
if ($compare($left[0], $right[0]) < 0) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
return array_merge($result, $left, $right);
}
$data = [
["name" => "Alice", "age" => 25],
["name" => "Bob", "age" => 20],
["name" => "Charlie", "age" => 30],
];
$sorted = mergeSortCustom($data, function($a, $b) {
return $a["age"] - $b["age"];
});
print_r($sorted);
?>With this version, you can sort anything you like, whether it’s user records, products, or scores. The custom comparator gives the power to define your own sorting rules, making the algorithm extremely flexible for real web applications.
Program 6: Merge Sort as an Object-Oriented PHP Class
This version wraps the Merge Sort algorithm inside a class, which is useful when building larger applications that require reusability and organization.
<?php
class MergeSorter {
public function sort($array) {
if (count($array) <= 1) {
return $array;
}
$mid = intdiv(count($array), 2);
$left = $this->sort(array_slice($array, 0, $mid));
$right = $this->sort(array_slice($array, $mid));
return $this->merge($left, $right);
}
private function merge($left, $right) {
$merged = [];
while (!empty($left) && !empty($right)) {
if ($left[0] <= $right[0]) {
$merged[] = array_shift($left);
} else {
$merged[] = array_shift($right);
}
}
return array_merge($merged, $left, $right);
}
}
$data = [50, 23, 9, 18, 61, 32];
$sorter = new MergeSorter();
$result = $sorter->sort($data);
print_r($result);
?>Object-oriented code keeps everything structured and reusable. Beginners who are learning classes in PHP will appreciate how the sorting logic is neatly packaged into one place. This makes the algorithm easy to use in projects where organization matters.
Program 7: Merge Sort Without Using array_shift()
This version avoids array_shift(), which can be slow for large arrays due to reindexing. Instead, it uses index pointers to make the merge process faster.
<?php
function mergeSortIndexed($array) {
if (count($array) <= 1) {
return $array;
}
$mid = intdiv(count($array), 2);
$left = mergeSortIndexed(array_slice($array, 0, $mid));
$right = mergeSortIndexed(array_slice($array, $mid));
return mergeIndexed($left, $right);
}
function mergeIndexed($left, $right) {
$merged = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) {
$merged[] = $left[$i++];
} else {
$merged[] = $right[$j++];
}
}
while ($i < count($left)) {
$merged[] = $left[$i++];
}
while ($j < count($right)) {
$merged[] = $right[$j++];
}
return $merged;
}
$data = [21, 1, 45, 78, 3, 5];
$result = mergeSortIndexed($data);
print_r($result);
?>This technique is better for performance. Instead of removing items from the beginning of the array, it simply moves through indexes. It helps beginners understand that the same algorithm can be written in different ways to improve speed and memory efficiency.
Frequently Asked Questions (FAQ)
This section answers popular questions beginners ask when learning Merge Sort in PHP.
Q1. Why is Merge Sort faster than simple sorting algorithms?
It divides the list into smaller sections and sorts them efficiently, giving it a stable performance of O(n log n).
Q2. Does Merge Sort work well with large datasets?
Yes. It is one of the most dependable algorithms for large datasets because its performance remains consistent.
Q3. Is Merge Sort stable?
Yes. It preserves the order of equal elements, making it a stable algorithm.
Q4. Can Merge Sort sort strings and custom data?
Absolutely. As long as you provide a clear comparison rule, Merge Sort can handle any data type.
Q5. Why does Merge Sort require extra memory?
Because it creates new arrays during merging, it uses additional space compared to in-place algorithms.
Conclusion
Merge Sort is one of the most reliable and efficient sorting algorithms you can learn in PHP. Its divide-and-conquer approach makes it both powerful and predictable, especially when working with large datasets. By exploring different versions—basic recursion, tracing, string sorting, descending order, and custom comparator—you now have a full understanding of how flexible this algorithm can be. Keep experimenting with different data types and logic to strengthen your grasp of sorting and algorithm design. With regular practice, these concepts become second nature, helping you grow into a more confident and skilled PHP developer.
