Sorting is one of the most fundamental problems in computer science, playing a critical role in data processing, search algorithms, and many other applications. This article will delve into various sorting algorithms in JavaScript, including their implementations, time complexity analysis, and applicable scenarios.
Classification of Sorting Algorithms
Sorting algorithms can be classified based on different criteria:
- By Time Complexity:
- O(n²): Bubble Sort, Selection Sort, Insertion Sort
- O(n log n): Merge Sort, Quick Sort, Heap Sort
- O(n): Counting Sort, Bucket Sort, Radix Sort (under specific conditions)
- By Stability:
- Stable Sorting: The relative order of equal elements remains unchanged after sorting
- Unstable Sorting: The relative order of equal elements may change
- By Space Complexity:
- In-Place Sorting: O(1) extra space (e.g., Heap Sort, Quick Sort)
- Non-In-Place Sorting: Requires extra space (e.g., Merge Sort)
Bubble Sort
Implementation
function bubbleSort(arr) {
const n = arr.length;
let swapped;
do {
swapped = false;
for (let i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
// Swap elements
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
// After each pass, the largest element "bubbles" to the end
n--;
} while (swapped);
return arr;
}
Optimized Version
function optimizedBubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
// If no swapping occurs, the array is already sorted
if (!swapped) break;
}
return arr;
}
Time Complexity
- Best Case: O(n) (already sorted array)
- Worst Case: O(n²) (reverse sorted array)
- Average Case: O(n²)
Space Complexity
O(1) (in-place sorting)
Stability
Stable sorting
Selection Sort
Implementation
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
// Find the minimum element in the unsorted portion
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first unsorted element
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
Time Complexity
- Best Case: O(n²)
- Worst Case: O(n²)
- Average Case: O(n²)
Space Complexity
O(1) (in-place sorting)
Stability
Unstable sorting (swapping may occur when the minimum element is not at the current position)
Insertion Sort
Implementation
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
const current = arr[i];
let j = i - 1;
// Insert the current element into the correct position in the sorted portion
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
Time Complexity
- Best Case: O(n) (already sorted array)
- Worst Case: O(n²) (reverse sorted array)
- Average Case: O(n²)
Space Complexity
O(1) (in-place sorting)
Stability
Stable sorting
Shell Sort
Implementation
function shellSort(arr) {
const n = arr.length;
let gap = Math.floor(n / 2);
while (gap > 0) {
for (let i = gap; i < n; i++) {
const temp = arr[i];
let j = i;
// Perform insertion sort on subarrays with gap
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
Time Complexity
- Best Case: Depends on the gap sequence
- Worst Case: O(n²) (for certain gap sequences)
- Average Case: Between O(n log n) and O(n²)
Space Complexity
O(1) (in-place sorting)
Stability
Unstable sorting
Merge Sort
Implementation
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) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
Time Complexity
- Best Case: O(n log n)
- Worst Case: O(n log n)
- Average Case: O(n log n)
Space Complexity
O(n) (requires extra space for temporary arrays)
Stability
Stable sorting
Quick Sort
Implementation
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
Optimized Version (Median-of-Three Pivot Selection)
function getMedianOfThree(arr, left, right) {
const mid = Math.floor((left + right) / 2);
if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
if (arr[mid] > arr[right]) [arr[mid], arr[right]] = [arr[right], arr[mid]];
return mid;
}
function quickSortOptimized(arr, left = 0, right = arr.length - 1) {
if (left < right) {
// Select pivot and partition
const pivotIndex = partitionOptimized(arr, left, right);
quickSortOptimized(arr, left, pivotIndex - 1);
quickSortOptimized(arr, pivotIndex + 1, right);
}
return arr;
}
function partitionOptimized(arr, left, right) {
// Median-of-three pivot selection
const median = getMedianOfThree(arr, left, right);
[arr[median], arr[right]] = [arr[right], arr[median]];
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
Time Complexity
- Best Case: O(n log n) (when partitions are balanced)
- Worst Case: O(n²) (already sorted or reverse sorted array with poor pivot choice)
- Average Case: O(n log n)
Space Complexity
O(log n) (recursive call stack)
Stability
Unstable sorting (partitioning may change the order of equal elements)
Heap Sort
Implementation
function heapSort(arr) {
const n = arr.length;
// Build max heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements one by one
for (let i = n - 1; i > 0; i--) {
// Move current root (maximum) to the end
[arr[0], arr[i]] = [arr[i], arr[0]];
// Heapify the remaining elements
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i; // Initialize largest as root
const left = 2 * i + 1;
const right = 2 * i + 2;
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than current largest
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
Time Complexity
- Best Case: O(n log n)
- Worst Case: O(n log n)
- Average Case: O(n log n)
Space Complexity
O(1) (in-place sorting)
Stability
Unstable sorting
Counting Sort
Implementation
function countingSort(arr) {
if (arr.length === 0) return arr;
// Find the maximum and minimum values in the array
const max = Math.max(...arr);
const min = Math.min(...arr);
const range = max - min + 1;
// Create counting array
const count = new Array(range).fill(0);
const output = new Array(arr.length);
// Count occurrences of each element
for (const num of arr) {
count[num - min]++;
}
// Calculate cumulative counts
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// Build sorted array based on counts
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}
Time Complexity
- Best Case: O(n + k) (k is the data range)
- Worst Case: O(n + k)
- Average Case: O(n + k)
Space Complexity
O(n + k)
Stability
Stable sorting
Bucket Sort
Implementation
function bucketSort(arr, bucketSize = 5) {
if (arr.length === 0) return arr;
// Find the minimum and maximum values in the array
const min = Math.min(...arr);
const max = Math.max(...arr);
// Calculate number of buckets
const bucketCount = Math.floor((max - min) / bucketSize) + 1;
const buckets = Array.from({ length: bucketCount }, () => []);
// Distribute elements into buckets
for (const num of arr) {
const bucketIndex = Math.floor((num - min) / bucketSize);
buckets[bucketIndex].push(num);
}
// Sort each bucket (using insertion sort here)
const sortedArr = [];
for (const bucket of buckets) {
insertionSort(bucket); // Use previously implemented insertion sort
sortedArr.push(...bucket);
}
return sortedArr;
}
Time Complexity
- Best Case: O(n + k) (all elements evenly distributed in buckets)
- Worst Case: O(n²) (all elements in one bucket)
- Average Case: O(n + n²/k + k) (k is the number of buckets)
Space Complexity
O(n + k)
Stability
Depends on the sorting algorithm used within buckets
Radix Sort
Implementation
function radixSort(arr) {
if (arr.length === 0) return arr;
// Find the maximum value to determine the number of digits
const max = Math.max(...arr);
// Perform counting sort for each digit
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
return arr;
}
function countingSortByDigit(arr, exp) {
const n = arr.length;
const output = new Array(n).fill(0);
const count = new Array(10).fill(0);
// Count occurrences of each digit
for (const num of arr) {
const digit = Math.floor(num / exp) % 10;
count[digit]++;
}
// Calculate cumulative counts
for (let i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build sorted array based on counts
for (let i = n - 1; i >= 0; i--) {
const digit = Math.floor(arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// Copy sorted results back to original array
for (let i = 0; i < n; i++) {
arr[i] = output[i];
}
}
Time Complexity
- Best Case: O(d(n + k)) (d is the number of digits, k is the radix)
- Worst Case: O(d(n + k))
- Average Case: O(d(n + k))
Space Complexity
O(n + k)
Stability
Stable sorting
Comparison of Sorting Algorithms
| Algorithm | Average Time Complexity | Best Case | Worst Case | Space Complexity | Stability | Applicable Scenarios |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n) | O(n²) | O(1) | Stable | Teaching, small-scale data |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Unstable | Teaching |
| Insertion Sort | O(n²) | O(n) | O(n²) | O(1) | Stable | Small-scale data, partially sorted data |
| Shell Sort | O(n log n) ~ O(n²) | Depends on gap sequence | O(n²) | O(1) | Unstable | Medium-scale data |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable | Large-scale data, stable sorting needs |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Unstable | Large-scale general sorting |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Unstable | In-place sorting, priority queue implementation |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Stable | Known, small data range |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Depends | Evenly distributed data |
| Radix Sort | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | Stable | Large-scale integer or string sorting |
Performance Optimization Techniques
- Quick Sort Optimization:
- Use median-of-three for pivot selection
- Switch to insertion sort for small subarrays
- Tail recursion optimization to reduce stack depth
- Merge Sort Optimization:
- Switch to insertion sort for small subarrays
- Check if already sorted to avoid unnecessary merges
- General Advice:
- For small-scale data (n < 10), insertion sort is often faster than O(n log n) algorithms
- For nearly sorted data, insertion sort or bubble sort may be more efficient
- Consider data characteristics (e.g., whether partially sorted, data range) to choose the appropriate algorithm
Practical Application Examples
Array Deduplication and Sorting
function uniqueAndSort(arr) {
// Deduplicate first
const unique = [...new Set(arr)];
// Then sort
return unique.sort((a, b) => a - b);
}
console.log(uniqueAndSort([3, 1, 2, 2, 4, 3])); // [1, 2, 3, 4]
Sorting Array of Custom Objects
const users = [
{ name: 'Alice', age: 25 },
{ name: 'Bob', age: 30 },
{ name: 'Charlie', age: 20 }
];
// Sort by age in ascending order
users.sort((a, b) => a.age - b.age);
// Sort by name in alphabetical order
users.sort((a, b) => a.name.localeCompare(b.name));
Large-Scale Data Sorting (External Sorting)
For large-scale data that cannot fit into memory at once, external sorting can be used:
- Divide the data into multiple small chunks, sort each chunk, and write to disk
- Use a multi-way merge algorithm to combine these sorted chunks into a single sorted sequence
Summary
JavaScript provides the built-in Array.prototype.sort() method, but understanding the principles and implementations of various sorting algorithms remains highly valuable for specific scenarios or performance-critical applications. Choosing the appropriate sorting algorithm requires considering:
- Data scale
- Initial state of data (whether partially sorted)
- Data characteristics (e.g., data range, presence of duplicates)
- Memory constraints
- Whether stability is required
In most practical development scenarios, the built-in sort() method is sufficient, but for specialized requirements or learning data structures, a deep understanding of these sorting algorithms is invaluable.
