Sorting is a crucial concept in programming. Whether you are arranging numbers, organizing text, or preparing data for analysis, efficient sorting makes your programs faster and more reliable. Tim Sort is one of the modern sorting algorithms that combines the simplicity of insertion sort with the efficiency of merge sort. It is widely used in programming languages like Python and Java for sorting arrays and lists because it handles real-world data effectively.
with hands-on learning.
get the skills and confidence to land your next move.
Tim Sort works by dividing the array into small sections called “runs” and then sorting these runs using insertion sort. Afterward, it merges the sorted runs using a process similar to merge sort. This hybrid approach makes it faster and more stable, particularly when the data is partially sorted, which is often the case in real applications. Learning Tim Sort in PHP helps beginners understand how combining simple algorithms can create a highly efficient sorting technique suitable for real-world use.
Program 1: Basic Tim Sort Using Loops
This program demonstrates a straightforward way of implementing Tim Sort in PHP. It sorts a predefined array of numbers in ascending order.
<?php
function insertionSort(&$arr, $left, $right) {
for ($i = $left + 1; $i <= $right; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= $left && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
function merge(&$arr, $l, $m, $r) {
$len1 = $m - $l + 1;
$len2 = $r - $m;
$left = array_slice($arr, $l, $len1);
$right = array_slice($arr, $m + 1, $len2);
$i = 0; $j = 0; $k = $l;
while ($i < $len1 && $j < $len2) {
if ($left[$i] <= $right[$j]) {
$arr[$k++] = $left[$i++];
} else {
$arr[$k++] = $right[$j++];
}
}
while ($i < $len1) $arr[$k++] = $left[$i++];
while ($j < $len2) $arr[$k++] = $right[$j++];
}
function timSort(&$arr) {
$n = count($arr);
$RUN = 32;
for ($i = 0; $i < $n; $i += $RUN) {
insertionSort($arr, $i, min(($i + $RUN - 1), ($n - 1)));
}
for ($size = $RUN; $size < $n; $size = 2 * $size) {
for ($left = 0; $left < $n; $left += 2 * $size) {
$mid = $left + $size - 1;
$right = min(($left + 2 * $size - 1), ($n - 1));
if ($mid < $right) merge($arr, $left, $mid, $right);
}
}
}
$array = [5, 21, 7, 23, 19, 10, 3, 15];
timSort($array);
echo "Sorted Array: ";
print_r($array);
?>This program first sorts small runs using insertion sort and then merges them progressively. Beginners can see how dividing data into manageable chunks can make sorting easier and more efficient. Tim Sort’s approach ensures better performance than using insertion sort alone on large arrays.
Program 2: Tim Sort Using a Function for Reusability
Here, we encapsulate the Tim Sort algorithm into a reusable function so you can sort any array easily.
<?php
function timSortFunction($arr) {
$RUN = 32;
$n = count($arr);
function insertionSortFunc(&$arr, $left, $right) {
for ($i = $left + 1; $i <= $right; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= $left && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
function mergeFunc(&$arr, $l, $m, $r) {
$left = array_slice($arr, $l, $m - $l + 1);
$right = array_slice($arr, $m + 1, $r - $m);
$i = 0; $j = 0; $k = $l;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) $arr[$k++] = $left[$i++];
else $arr[$k++] = $right[$j++];
}
while ($i < count($left)) $arr[$k++] = $left[$i++];
while ($j < count($right)) $arr[$k++] = $right[$j++];
}
for ($i = 0; $i < $n; $i += $RUN) insertionSortFunc($arr, $i, min(($i + $RUN - 1), ($n - 1)));
for ($size = $RUN; $size < $n; $size *= 2) {
for ($left = 0; $left < $n; $left += 2 * $size) {
$mid = $left + $size - 1;
$right = min(($left + 2 * $size - 1), ($n - 1));
if ($mid < $right) mergeFunc($arr, $left, $mid, $right);
}
}
return $arr;
}
$array = [12, 4, 7, 9, 1, 15, 6];
$sortedArray = timSortFunction($array);
echo "Sorted Array using Function: ";
print_r($sortedArray);
?>Encapsulating Tim Sort in a function makes it reusable and keeps the code organized. Beginners can now call a single function to sort any dataset, making the algorithm easier to understand and apply in multiple situations.
Program 3: Tim Sort for Descending Order
This program demonstrates how Tim Sort can sort arrays in descending order by simply changing the comparison in insertion sort and merge steps.
<?php
function timSortDescending(&$arr) {
$n = count($arr);
$RUN = 32;
function insertionSortDesc(&$arr, $left, $right) {
for ($i = $left + 1; $i <= $right; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= $left && $arr[$j] < $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
function mergeDesc(&$arr, $l, $m, $r) {
$left = array_slice($arr, $l, $m - $l + 1);
$right = array_slice($arr, $m + 1, $r - $m);
$i = 0; $j = 0; $k = $l;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] >= $right[$j]) $arr[$k++] = $left[$i++];
else $arr[$k++] = $right[$j++];
}
while ($i < count($left)) $arr[$k++] = $left[$i++];
while ($j < count($right)) $arr[$k++] = $right[$j++];
}
for ($i = 0; $i < $n; $i += $RUN) insertionSortDesc($arr, $i, min(($i + $RUN - 1), ($n - 1)));
for ($size = $RUN; $size < $n; $size *= 2) {
for ($left = 0; $left < $n; $left += 2 * $size) {
$mid = $left + $size - 1;
$right = min(($left + 2 * $size - 1), ($n - 1));
if ($mid < $right) mergeDesc($arr, $left, $mid, $right);
}
}
}
$array = [5, 2, 9, 1, 7, 3];
timSortDescending($array);
echo "Descending Sorted Array: ";
print_r($array);
?>Changing the comparison operators allows the same algorithm to sort data from highest to lowest. Beginners learn that small adjustments can change the behavior of an algorithm, demonstrating flexibility and real-world utility.
Program 4: Tim Sort for Strings
Tim Sort can also sort text data alphabetically. This program shows how to order a list of animal names.
<?php
function timSortStrings(&$arr) {
$n = count($arr);
$RUN = 32;
function insertionSortStrings(&$arr, $left, $right) {
for ($i = $left + 1; $i <= $right; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= $left && strcmp($arr[$j], $key) > 0) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
function mergeStrings(&$arr, $l, $m, $r) {
$left = array_slice($arr, $l, $m - $l + 1);
$right = array_slice($arr, $m + 1, $r - $m);
$i = 0; $j = 0; $k = $l;
while ($i < count($left) && $j < count($right)) {
if (strcmp($left[$i], $right[$j]) <= 0) $arr[$k++] = $left[$i++];
else $arr[$k++] = $right[$j++];
}
while ($i < count($left)) $arr[$k++] = $left[$i++];
while ($j < count($right)) $arr[$k++] = $right[$j++];
}
for ($i = 0; $i < $n; $i += $RUN) insertionSortStrings($arr, $i, min(($i + $RUN - 1), ($n - 1)));
for ($size = $RUN; $size < $n; $size *= 2) {
for ($left = 0; $left < $n; $left += 2 * $size) {
$mid = $left + $size - 1;
$right = min(($left + 2 * $size - 1), ($n - 1));
if ($mid < $right) mergeStrings($arr, $left, $mid, $right);
}
}
}
$animals = ["Zebra", "Elephant", "Lion", "Monkey", "Cat"];
timSortStrings($animals);
echo "Alphabetically Sorted Animals: ";
print_r($animals);
?>Using strcmp, the algorithm can handle strings effectively. Beginners can see that Tim Sort is not limited to numbers but can manage real-world text data such as names, product lists, or titles.
Program 5: Tim Sort Using Recursion for Merge
This program demonstrates a recursive approach for the merging process, which can help beginners understand recursion in a practical scenario.
<?php
function recursiveMerge(&$arr, $left, $mid, $right) {
$leftArr = array_slice($arr, $left, $mid - $left + 1);
$rightArr = array_slice($arr, $mid + 1, $right - $mid);
$i = 0; $j = 0; $k = $left;
while ($i < count($leftArr) && $j < count($rightArr)) {
if ($leftArr[$i] <= $rightArr[$j]) $arr[$k++] = $leftArr[$i++];
else $arr[$k++] = $rightArr[$j++];
}
while ($i < count($leftArr)) $arr[$k++] = $leftArr[$i++];
while ($j < count($rightArr)) $arr[$k++] = $rightArr[$j++];
}
function timSortRecursive(&$arr, $left, $right) {
$RUN = 32;
if ($right - $left + 1 <= $RUN) {
for ($i = $left + 1; $i <= $right; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= $left && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return;
}
$mid = floor(($left + $right) / 2);
timSortRecursive($arr, $left, $mid);
timSortRecursive($arr, $mid + 1, $right);
recursiveMerge($arr, $left, $mid, $right);
}
$array = [20, 7, 12, 18, 5, 2, 15];
timSortRecursive($array, 0, count($array) - 1);
echo "Sorted Array using Recursive Merge: ";
print_r($array);
?>This example introduces recursion in merging, helping beginners learn how breaking problems into smaller pieces simplifies complex operations. It reinforces the hybrid nature of Tim Sort, combining insertion sort and recursive merging effectively.
Frequently Asked Questions (FAQ)
Tim Sort is a versatile algorithm, and beginners often have several questions about it.
Q1: Why is Tim Sort preferred in real applications?
Tim Sort is stable, efficient, and handles partially sorted data very well. This makes it practical for many real-world scenarios.
Q2: Can Tim Sort handle strings and numbers together?
Yes, Tim Sort can handle both numbers and strings, but mixing data types in the same array is not recommended.
Q3: What makes Tim Sort faster than insertion sort alone?
It divides data into small runs, sorts them, and merges efficiently. This reduces comparisons and shifts compared to sorting the entire array at once.
Q4: Is Tim Sort a stable algorithm?
Yes, Tim Sort preserves the original order of equal elements, which is important for applications like sorting names or records.
Q5: Can beginners implement Tim Sort easily in PHP?
Yes, by following examples using loops, functions, and recursion, beginners can understand and implement Tim Sort effectively.
Conclusion
Tim Sort is a practical and powerful sorting algorithm for both beginners and advanced programmers. By combining the simplicity of insertion sort with the efficiency of merge sort, it handles real-world data efficiently. Through these PHP examples, learners can practice sorting numbers, strings, and explore recursion. Mastering Tim Sort builds a strong foundation in algorithm design and prepares you to explore more advanced sorting techniques. Practicing these programs will make you more confident in handling data in your PHP projects.
