Hello, aspiring programmers! Today's topic is Merge Sort. Merge Sort is a sorting technique, much like arranging a deck of shuffled cards in order. However, for data on the Internet scale, Merge Sort outperforms your regular techniques. Today, we'll explore Merge Sort, code it in PHP, and analyze its speed. Ready? Let's get started!
What is Merge Sort?
In computer science, Merge Sort is a popular method for sorting elements. Merge Sort uses the same 'divide-and-conquer' strategy for sorting as the familiar Quick Sort algorithm. Imagine you have one long music playlist mixed up with songs. You want to sort these songs from A to Z. That's what Merge Sort does to an array.
The three steps of Merge Sort are:
Split the array into halves.
Sort each half separately.
Merge the sorted halves back together.
Understanding the Merge Process
Merging the Halves Back Together
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal
We will start by building a code for merging two sorted parts. The merge process makes the two halves play sort and seek. It compares elements from two halves and merges them so that the resulting list is also sorted.
Let's code a merge() function in PHP that will do just that. Note that the final variant of the merge sort function will perform every operation "in place," meaning there will not actually be two arrays; we will operate on parts of one array. With this in mind, let's implement the merge function to take just one array and treat its parts as separate arrays.
function merge(&$arr, $left, $mid, $right) { $n1 = $mid - $left + 1; // Find number of elements in the left array $Left = array(); // Define left array $n2 = $right - $mid; // Find number of elements in the right array $Right = array(); // Define right array // Let's fill in these arrays for ($i = 0; $i < $n1; $i++) $Left[$i] = $arr[$left + $i]; for ($j = 0; $j < $n2; $j++) $Right[$j] = $arr[$mid + 1 + $j];}
So far, we've divided our original list into two halves, Left and Right.
Although seemingly tricky, the code is quite straightforward: We place two pointers, $i and $j, at the beginning of the Right and Left arrays. We choose the smaller element, put it in the final array $arr, and move the corresponding pointer further. We keep doing this until one of the pointers reaches the end of its array.
Handling Leftovers
Implementing Divide and Conquer Strategy
Now, let's implement the method to divide the array into two halves. Code-wise, we'll need to define a sort() method to split the array and manage the merge process. We will split the array and its halves recursively until we end up with small arrays of just one element, which are naturally sorted! Next, we will merge these arrays back together into one big sorted array.
Splitting the Array into Halves
Marshalling the Merge Process
Decoding Merge Sort Efficiency
In the computing world, performance matters. The less time it takes for a sorting algorithm to run, the better. Merge Sort shows good performance with a time complexity of O(n log n), similar to sorting a huge deck of cards quickly. Thus, it excels when dealing with massive data sets.
Strengths and Pitfalls of Merge Sort
Merge Sort is consistent. It's like a reliable late-night tutor that offers predictable performance, regardless of the initial order of the data input. It mimics a dependable friend who will not let you down.
However, it tends to use extra memory, creating new arrays during the merge process.
Ending Notes and Looking Ahead
Great job! We've broken down Merge Sort and coded it in PHP. Next up, we have some exciting hands-on exercises for you. Ready to put what you've learned into practice? Let's dive into the fun part! Let's get coding!
We stop the process when one of the pointers reaches the end of its array, but some elements could be left in the other array.
To handle this, let's copy the remaining elements of both arrays (if any) to the end of the resulting $arr array.
// Copy remaining elements of Left[] if any while ($i < $n1) { $arr[$k] = $Left[$i]; $i++; $k++; } // Copy remaining elements of Right[] if any while ($j < $n2) { $arr[$k] = $Right[$j]; $j++; $k++; }
The merge section is completed. It successfully merges two halves back together in the sorted order.
Let's start by building the sort() method. Initially, we'll handle the splitting part:
function sort(&$arr, $left, $right) { if ($left < $right) { $mid = intval(($left + $right) / 2); // Finding the midpoint }}
Now, we can split our list into two halves, but they still need to be sorted.
Next, we need to sort these halves and merge them together:
sort($arr, $left, $mid); // Sorting the left half sort($arr, $mid + 1, $right); // Sorting the right half merge($arr, $left, $mid, $right); // Merging the sorted halves }}
Phew! We've now implemented our Merge Sort algorithm in PHP.
PHP
function merge(&$arr, $left, $mid, $right) { $n1 = $mid - $left + 1; // Find number of elements in the left array $Left = array(); // Define left array $n2 = $right - $mid; // Find number of elements in the right array $Right = array(); // Define right array // Let's fill in these arrays for ($i = 0; $i < $n1; $i++) $Left[$i] = $arr[$left + $i]; for ($j = 0; $j < $n2; $j++) $Right[$j] = $arr[$mid + 1 + $j];}
// Copy remaining elements of Left[] if any while ($i < $n1) { $arr[$k] = $Left[$i]; $i++; $k++; } // Copy remaining elements of Right[] if any while ($j < $n2) { $arr[$k] = $Right[$j]; $j++; $k++; }
PHP
function sort(&$arr, $left, $right) { if ($left < $right) { $mid = intval(($left + $right) / 2); // Finding the midpoint }}
PHP
sort($arr, $left, $mid); // Sorting the left half sort($arr, $mid + 1, $right); // Sorting the right half merge($arr, $left, $mid, $right); // Merging the sorted halves }}
