Sorting Algorithms in PHP: Quick Sort, Merge Sort, and Bubble Sort

Sorting algorithms are important when it comes to working with data suitable for web applications and databases. Regardless of whether you are implementing solutions for major online stores, databases, or search engines, the choice of a sorting algorithm can significantly affect performance.

In this article we will compare three important sorting algorithms which are Quick Sort, Merge Sort and Bubble Sort and we will also provide the PHP implementations of it. When exploring different algorithms, which are outlined below, it is fundamental to compare the time complexity, and advantages, and identify the relevant applications. However, before we discuss the differences, let’s first refresh our memory with the Big O notation. It will assist you when analyzing the time complexities of the sorting algorithms in this knowledge.

Understanding Big O Notation

Big O notation is a special kind of mathematical notation used to express time and space complexity of an algorithm. It offers an indication of the greatest level of growth of an algorithm’s run time or memory usage against the size of input data. This notation enables the developers to know how an algorithm is going to perform and scale for larger datasets. Here are some key points about Big O notation:

O(1): Linear time—no matter the number of elements, the time taken to solve the problem is linear
O(n): The run time increases with the input size—the model is O(n) in the size of the domain.
O(n log n): Linear — time more than proportionately increases with the size of the input, this is typical with efficient sorting algorithms.
O(n²): Quadratic time—reached in the instances where simpler sorting algorithms such as Bubble sort are applied, and the run time will increase with bigger inputs.

Knowledge of these difficulties helps in case selection of the approach for the particular problem, proper work in practice between the speed of calculations and consumption of resources.

Sorting Algorithms: Introduction

Sorting techniques make lists more efficient and easier to search by rearranging its content. They are all different from each other and have their own advantages and disadvantages when deciding to choose one particular algorithm, certain parameters should be taken into account such as the size of data set to be processed, stability of the algorithm and memory usage.

1. Quick Sort Algorithm in PHP

Quick Sort is well known, fast sorting algorithm available in PHP and it works greatly. It uses the divide and conquer strategy to rearrange the elements – selecting a “pivot”, and then sorting the array into two sub-arrays; with elements lower than the pivot and the other sub-array with elements higher than the pivot.

How Quick Sort Works:

One pivot element is chosen from the given array.
The array is partitioned into two halves: We divide the elements into less than the pivot and elements more than the pivot in a sorted manner.
Continually, the algorithm applies the above method to the sub-arrays until array is completely sorted.

Quick Sort Code in PHP:

<?php
function quickSort($arr) {
    if (count($arr) < 2) {
        return $arr; // Base case for recursion
    }
    
    $pivot = $arr[0]; // Select the pivot element
    $less = array_filter(array_slice($arr, 1), function($x) use ($pivot) { return $x <= $pivot; });
    $greater = array_filter(array_slice($arr, 1), function($x) use ($pivot) { return $x > $pivot; });

    return array_merge(quickSort($less), [$pivot], quickSort($greater));
}

// Example usage
$array = [64, 34, 25, 12, 22, 11, 90];
$sortedArray = quickSort($array);
print_r($sortedArray);
?>

Quick Sort Time Complexity:

Best case: O(n log n) — the case arises when the pivot separates array elements into almost equal parts.
Average case: O(n log n) — runs most of the times.
Worst case: O(n²) — occurs when the pivot divides the array unevenly (e.g., already sorted arrays).

Advantages:

In-place sorting: In-place sorting: The essence of Quick Sort is that it uses the least possible amount of memory.
High performance: It’s usually faster than other algorithms like the Merge Sort.
Customizable pivot strategies: It is possible to enhance the performance by using some change of selection approach to the pivot (random pivot instead of the median).

Disadvantages:

Unstable: The order need not be preserved for any of its elements if they are equal.
Worst-case performance: Rare cases have the running time of O(n²), but these are extremely rare if we only design a better pivot strategy.

Best Use Cases:

When working with big data, when computational speed, as well as memory usage, is crucial.

2. Merge Sort Algorithm in PHP

Among all sorting algorithms, Merge Sort is one of the most efficient and stable algorithms, efficient in the sense that its time complexity is O(n log n) of the best and the worst case.This one takes the array and splits it into two parts, sorts each of these two halves, and then combines the two parts in the order of sorting.

How Merge Sort Works:

The array is then bisected into two sub array until every sub array is equal to one element.
The sub-arrays are then combined in a sorted manner and hence provides us a sorted array at the end.

Merge Sort Code in PHP:

<?php
function mergeSort($arr) {
    if (count($arr) < 2) {
        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 = $j = 0;

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

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

// Example usage
$array = [64, 34, 25, 12, 22, 11, 90];
$sortedArray = mergeSort($array);
print_r($sortedArray);
?>

Merge Sort Time Complexity:

Best case: O(n log n) — for all the cases.
Average case: O(n log n) — a guarantee of the program’s time efficiency.
Worst case: O(n log n) — no degradation in performance.

Advantages:

Stable sorting: It maintains the relative order of same items.
Guaranteed performance: O(n log n) in all cases, including the worst case.
Optimal for linked lists: Linked list is well sorted by Merge Sort.

Disadvantages:

Memory overhead: Merge Sort requires extra space, space complexity: O(n) to merge the split sub arrays.
Slower in practice: Because it requires more memory, it takes longer than Quick sort in the case of small arrays.

Best Use Cases:

For medium to large data sets and where we do not want to have any fluctuation in the resulting arrangement.
Situations that involve consistent performance requirements, regardless of data ordering.

3. Bubble Sort Algorithm in PHP

Bubble Sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. Although it’s easy to implement, it is inefficient for large datasets.

How Bubble Sort Works:

The algorithm starts at the beginning of the array and compares each adjacent pair of elements, swapping them if needed.
This process is repeated until no swaps are needed, indicating that the array is sorted.

Bubble Sort Code in PHP:

<?php
function bubbleSort($arr) {
    $n = count($arr);
    
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // Swap adjacent elements
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    
    return $arr;
}

// Example usage
$array = [64, 34, 25, 12, 22, 11, 90];
$sortedArray = bubbleSort($array);
print_r($sortedArray);
?>

Bubble Sort Time Complexity:

Best case: O(n) — occurs when the array is already sorted.
Average case: O(n²) — requires multiple passes through the array.
Worst case: O(n²) — occurs when the array is reverse sorted.

Advantages:

Simple and easy to implement: Ideal for beginners learning sorting algorithms.
Efficient for small or nearly sorted arrays: Performs well with already sorted data.

Disadvantages:

Inefficient for large datasets: O(n²) time complexity makes it impractical for large arrays.
High number of comparisons: Even when the array is nearly sorted, Bubble Sort still compares many elements.

Best Use Cases:

Very small datasets or arrays that are nearly sorted.
Educational purposes to explain sorting concepts.

Summary of Sorting Algorithms in PHP

Here’s a breakdown of each algorithm’s strengths, weaknesses, and best use cases:

Algorithm	Best Case	Average Case	Worst Case	Stability	Space Complexity	Best Use Cases
Quick Sort	O(n log n)	O(n log n)	O(n²)	No	O(log n)	Large datasets requiring in-place sorting
Merge Sort	O(n log n)	O(n log n)	O(n log n)	Yes	O(n)	Stable sorting, consistent performance
Bubble Sort	O(n)	O(n²)	O(n²)	Yes	O(1)	Small or nearly sorted datasets

Conclusion

Of all the sorting algorithms presented, Quick Sort has the best performance on large data and nearly negligible memory use, making it suitable for most applications. Nevertheless, if stability is at issue, and you might need to preserve the relative positions of equal values, are used, Merge Sort is a perfect tool because its speed is and its sorting method is stable. While Bubble Sort is effective only for small arrays of data, and not for large ones, its main advantage includes its simplicity and applicability for educational purposes.

Subscribe to our newsletter!