3 JavaScript Array Sorting Algorithms and When to Use Them

Let’s compare three common JavaScript array sorting algorithms: Bubble Sort, Merge Sort, and Quick Sort. I’ll explain each, provide examples, and highlight when each would be most appropriate.

1. Bubble Sort

Description:
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

Time Complexity:

• Best: O(n)
• Average: O(n²)
• Worst: O(n²)

Example:

function bubbleSort(arr) {
    let swapped;
    do {
        swapped = false;
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // Swap
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
    } while (swapped);
    return arr;
}
const array = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(array)); // Output: [11, 12, 22, 25, 34, 64, 90]

When to Use:

• Use when you’re sorting small datasets.
• It’s primarily a learning tool, as it’s inefficient for large datasets.
• If the array is nearly sorted, Bubble Sort can be efficient.

2. Merge Sort

Description:
Merge Sort is a divide-and-conquer algorithm. It divides the array into two halves, recursively sorts each half, and then merges the two sorted halves back together.

Time Complexity:

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n log n)

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    let result = [], leftIndex = 0, rightIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

const array = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(array)); // Output: [11, 12, 22, 25, 34, 64, 90]

When to Use:

• Use when stability (preserving the order of equal elements) is important.
• Ideal for sorting large datasets.
• Particularly effective when memory usage isn’t a concern (uses extra space for splitting and merging).

3. Quick Sort

Description:
Quick Sort is another divide-and-conquer algorithm. It picks a pivot element, partitions the array into elements less than the pivot and elements greater than the pivot, and recursively sorts the partitions.

Time Complexity:

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n²) (though rare, typically happens when the pivot is poorly chosen)

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}

const array = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(array)); // Output: [11, 12, 22, 25, 34, 64, 90]

When to Use:

• Preferred for large datasets due to its average-case performance of O(n log n).
• In-place sorting (minimal memory usage) makes it more efficient than Merge Sort in terms of memory.
• Avoid when the dataset is nearly sorted or when the worst-case performance could cause problems (e.g., choosing the worst pivot leads to O(n²)).

Keep in mind, the last array element was chosen as a pivot point, but you may decide to change that strategy depending on the implementation. For instance, if you know your dataset is likely to be partially sorted already, it would be wise to pick a random pivot.

const pivotIndex = Math.floor(Math.random() * arr.length);

Summary and When to Use Each:

• Bubble Sort: Best for educational purposes or very small arrays. Rarely used in practice due to inefficiency on large datasets.
• Merge Sort: Use when you need consistent O(n log n) performance and stability. Ideal for large datasets where extra memory usage isn’t a concern.
• Quick Sort: Generally the best choice for large datasets when you want in-place sorting. It’s fast on average but can degrade to O(n²) in rare cases.

Each algorithm has its strengths, and the choice depends on the dataset’s size, structure, and requirements for memory and stability.