Sorting an array without using any PHP built-in functions is a common exercise in learning Data Structures and Algorithms (DSA). Let’s go through the main sorting algorithms and apply them manually to this sample array in PHP:
$arr = [5, 2, 9, 1, 5, 6];✅ Sorting Algorithms Covered
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
Then, we’ll discuss how to analyze time and space complexity.
1. 🔁 Bubble Sort (Basic, Easy)
Algorithm: Repeatedly swap adjacent elements if they are in the wrong order.
function bubbleSort(&$arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
// Swap
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
}✅ Time Complexity:
- Worst:
O(n^2) - Best (already sorted):
O(n) - Average:
O(n^2)
✅ Space Complexity:O(1)
2. 🔎 Selection Sort
Algorithm: Repeatedly find the minimum element and put it at the beginning.
function selectionSort(&$arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
// Swap
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}✅ Time Complexity: O(n^2) for all cases
✅ Space Complexity: O(1)
3. 📥 Insertion Sort
Algorithm: Build the sorted array one item at a time.
Insertion Sort builds the sorted array one item at a time by inserting each element into its correct position.
function insertionSort(&$arr) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}✅ Time Complexity:
- Worst:
O(n^2) - Best:
O(n)(when already sorted)
✅ Space Complexity:O(1)
4. 🔀 Merge Sort (Efficient, Divide and Conquer)
Algorithm: Divide array into halves, sort and merge recursively.
Merge Sort is a divide and conquer algorithm. It divides the array into halves, sorts each half, and then merges them back together.
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);
$left = mergeSort($left);
$right = mergeSort($right);
return merge($left, $right);
}
function merge($left, $right) {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}✅ Time Complexity: O(n log n)
✅ Space Complexity: O(n) (due to recursive calls and array merging)
5. ⚡ Quick Sort (Fastest in Practice)
Algorithm: Pick a pivot, partition array into sub-arrays, then sort recursively.
function quickSort($arr) {
if (count($arr) < 2) return $arr;
$pivot = $arr[0];
$left = $right = [];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] < $pivot) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
return array_merge(quickSort($left), [$pivot], quickSort($right));
}✅ Time Complexity:
- Best / Average:
O(n log n) - Worst:
O(n^2)(if pivot is always min/max)
✅ Space Complexity:O(log n)toO(n)(depends on recursion depth)
🧠 How to Calculate Time and Space Complexity
Time Complexity
- Count loops:
- One loop = O(n)
- Nested loop = O(n^2)
- Recursive calls:
- Divide-and-conquer: Merge Sort and Quick Sort = O(n log n)
Space Complexity
- Memory used in addition to input array:
- Extra arrays (merge, quick): O(n)
- No new arrays (bubble, selection, insertion): O(1)
✅ Example Execution
$arr = [5, 2, 9, 1, 5, 6];
bubbleSort($arr); // or selectionSort, insertionSort etc.
print_r($arr);Result (sorted array):
Array ( [0] => 1 [1] => 2 [2] => 5 [3] => 5 [4] => 6 [5] => 9 )