Sorting Algorithms Explained: A Complete Guide

1. Comparison-based sorting works by comparing pairs of elements and deciding which one comes first. Bubble sort, selection sort, insertion sort, merge sort, quicksort and heap sort all belong here. There's a hard mathematical limit on how well any comparison-based sort can perform across all possible inputs: no such algorithm can guarantee better than O(n log n) comparisons in the worst case, no matter how clever the implementation is. This isn't a guess. It comes from a simple counting argument (there are n! possible orderings of n items and each single comparison can only rule out at most half of the remaining possibilities) and it's one of the few "provably true" limits in this entire field.

That limit is about the guarantee, not about every single run. An individual algorithm can still be faster than O(n log n) on specific, favorable input. Insertion sort, for example, runs in O(n) on data that's already sorted. What the lower bound rules out is any comparison-based algorithm promising O(n log n) or better for every possible input, including the worst-arranged one.

2. Non-comparison-based sorting sidesteps that limit entirely by never comparing two elements directly. Counting sort, radix sort and bucket sort work this way, using the actual values (not comparisons) to figure out where things go. That's how they manage to beat O(n log n) under the right conditions.

1. Stable means that if two items are considered equal by the sorting rule, they keep their original relative order after sorting. This matters more than it sounds. Say you have a spreadsheet of employees, already sorted by name and you sort it again by department. A stable sort keeps everyone's name order intact within each department. An unstable sort might shuffle names around inside each department for no visible reason, which looks like a bug even though technically the department order is correct.

import java.util.*;

public class StabilityExample {
    record Employee(String name, String department) {}

    public static void main(String[] args) {
        List<Employee> employees = new ArrayList<>(List.of(
            new Employee("Ravi", "Sales"),
            new Employee("Meera", "Engineering"),
            new Employee("Amit", "Sales"),
            new Employee("Zoya", "Engineering"),
            new Employee("Karan", "Sales")
        ));

        employees.sort(Comparator.comparing(Employee::department));

        for (Employee e : employees) {
            System.out.println(e.name() + ", " + e.department());
        }
    }
}

// Meera, Engineering
// Zoya, Engineering
// Ravi, Sales
// Amit, Sales
// Karan, Sales

Notice Meera still comes before Zoya and Ravi, Amit and Karan keep their original order within Sales. That's stability in action and it's exactly why Java's List.sort() and Collections.sort() are documented as stable sorts.

2. In-place means the algorithm rearranges the data using little to no extra memory, instead of building a whole new sorted copy. Bubble sort, selection sort, insertion sort and quicksort (in their typical form) are in-place. Merge sort, in its usual array-based form, is not. It needs roughly as much extra memory as the input to hold the pieces being merged.

3. Adaptive means the algorithm gets faster automatically when the input is already partly sorted. Insertion sort is a great example: on data that's almost sorted already, it runs close to O(n) instead of O(n²), because there's barely anything left to move. Non-adaptive algorithms like standard merge sort do the same amount of work whether the input is a random mess or already 99% sorted.

1. Bubble Sort: The One Everyone Learns First

Bubble sort repeatedly walks through the array, comparing each pair of neighbors and swapping them if they're in the wrong order. After one full pass, the largest remaining value has "bubbled up" to its correct spot at the end, like a bubble rising to the top of water.

Real-life example: Picture kids lining up by height and the rule is simple: any two kids standing next to each other swap places if the one on the left is taller than the one on the right. Do that enough times across the whole line and eventually everyone ends up shortest to tallest, purely from neighbors swapping with neighbors.

Bubble sort on [5, 1, 4, 2] -- each pass bubbles the largest
remaining value to the end, like bubbles rising to the top

Pass 1:
  [5, 1, 4, 2]  compare 5,1 -> swap  -> [1, 5, 4, 2]
  [1, 5, 4, 2]  compare 5,4 -> swap  -> [1, 4, 5, 2]
  [1, 4, 5, 2]  compare 5,2 -> swap  -> [1, 4, 2, 5]
  End of pass 1: [1, 4, 2, 5]   (5 is now in its final place)

Pass 2:
  [1, 4, 2, 5]  compare 1,4 -> no swap
  [1, 4, 2, 5]  compare 4,2 -> swap  -> [1, 2, 4, 5]
  End of pass 2: [1, 2, 4, 5]

Pass 3:
  [1, 2, 4, 5]  compare 1,2 -> no swap
  No swaps at all this pass -- the array is already sorted,
  so a good implementation stops early here instead of
  running the remaining passes for nothing.

import java.util.Arrays;

public class BubbleSort {
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;   // already sorted, no need to keep going
        }
    }

    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2};
        bubbleSort(a);
        System.out.println(Arrays.toString(a));          // [1, 2, 4, 5]

        int[] b = {9, 8, 7, 6, 5};
        bubbleSort(b);
        System.out.println(Arrays.toString(b));          // [5, 6, 7, 8, 9]
    }
}

• Time complexity: best case O(n) with the early-exit check (already sorted, one pass confirms it), average and worst case O(n²).
• Space complexity: O(1), it sorts in place.
• Stable: yes.
• Honestly: bubble sort is almost never used in real production code. Its value is entirely educational, it's the easiest algorithm to trace by hand, which makes it a good first step before the faster, less intuitive ones.
• When not to use it: anywhere performance matters, which in practice means almost everywhere outside a classroom.

2. Selection Sort: Picking the Best Card Each Time

Selection sort repeatedly scans the unsorted part of the array to find the smallest remaining value, then swaps it into place at the front. It builds the sorted section one confirmed-correct item at a time.

Real-life example: You're organizing a messy hand of playing cards by going through the whole hand to find the smallest card, pulling it out and placing it first. Then you go through what's left to find the next smallest and place it second. Repeat until every card has a spot.

import java.util.Arrays;

public class SelectionSort {
    static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) minIdx = j;
            }
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }

    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2};
        selectionSort(a);
        System.out.println(Arrays.toString(a));          // [1, 2, 4, 5]

        int[] b = {10, 45, 2, 87};
        selectionSort(b);
        System.out.println(Arrays.toString(b));          // [2, 10, 45, 87]
    }
}

• Time complexity: O(n²) in every case, best, average and worst, because it always scans the full remaining unsorted section to find the minimum, even if the array is already sorted. That's actually its one distinguishing trait, unlike bubble or insertion sort, it can't get lucky.
• Space complexity: O(1).
• Stable: no, in its typical implementation. Swapping the found minimum into place can jump it past equal elements, changing their relative order.
• When to use it: almost never in real production systems, for the same reasons as bubble sort.
• It does have one genuine niche, when swapping is expensive but comparisons are cheap, selection sort makes the fewest possible swaps, exactly n - 1 of them, which can matter for very specific hardware-constrained situations.

3. Insertion Sort: How Humans Actually Sort Cards

Insertion sort builds a sorted section one item at a time by taking the next unsorted item and inserting it into the correct position among the already-sorted items before it.

Real-life example: This is actually how most people sort a hand of playing cards as they're dealt. You pick up a card and you slide it into the correct spot among the cards already in your hand, comparing it against the ones you're already holding. You never re-sort what's already sorted. You just find where the new card belongs.

import java.util.Arrays;

public class InsertionSort {
    static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2};
        insertionSort(a);
        System.out.println(Arrays.toString(a));          // [1, 2, 4, 5]

        int[] b = {1, 2, 3, 4};
        insertionSort(b);
        System.out.println(Arrays.toString(b));          // [1, 2, 3, 4] -- barely any work needed
    }
}

• Time complexity: best case O(n) on data that's already sorted or nearly sorted, since the inner loop barely moves anything. Average and worst case O(n²).
• Space complexity: O(1).
• Stable: yes.
• Adaptive: yes and this is its real strength.

Real-world usage: insertion sort's speed on small or nearly-sorted data has real practical weight, not just teaching value. Production sorting algorithms like Timsort (covered later in this guide) and many implementations of quicksort deliberately switch to insertion sort once a chunk of the array shrinks below a small threshold, often around 16 to 64 elements, because insertion sort actually beats more "advanced" algorithms at that size. Faster in theory doesn't always mean faster in practice and this is the cleanest example of that in the whole topic.

4. Merge Sort: Divide, Conquer and Combine

Merge sort splits the array in half again and again until each piece has just one element, then merges those pieces back together in sorted order, two at a time, all the way back up.

Real-life example: Two teachers each grade half a stack of exam papers and sort their own half by roll number. To combine the two sorted stacks into one, you don't reshuffle everything. You just keep comparing the top paper of each stack and taking whichever has the lower roll number, one at a time, until both stacks are empty. That merging step is the entire trick.

Merge sort on [6, 3, 8, 5] -- split all the way down, then merge back up

                        [6, 3, 8, 5]
                         /         \
                   [6, 3]           [8, 5]
                   /    \           /    \
                [6]    [3]       [8]    [5]
                   \    /           \    /
                  [3, 6]            [5, 8]
                    (merge: 3<6, so 3 first)
                         \         /
                       [3, 5, 6, 8]
                (merge: compare fronts of [3,6] and [5,8] one at a time)

Splitting never compares anything -- it's just cutting the array in
half. All the actual work happens while merging two already-sorted
halves back together, which is why merge sort's time is always
O(n log n): log n levels of splitting and O(n) work merging at each level.

import java.util.Arrays;

public class MergeSort {
    static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) return arr;
        int mid = arr.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));

        int[] result = new int[arr.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) result[k++] = left[i++];
            else result[k++] = right[j++];
        }
        while (i < left.length) result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeSort(new int[]{6, 3, 8, 5})));          // [3, 5, 6, 8]
        System.out.println(Arrays.toString(mergeSort(new int[]{9, 8, 7, 6, 5, 4})));    // [4, 5, 6, 7, 8, 9]
    }
}

• Time complexity: O(n log n) in the best, average and worst case. This consistency is merge sort's biggest selling point. It never has a bad day.
• Space complexity: O(n), since merging needs somewhere to build the combined result.
• Stable: yes, as long as the merge step always prefers the left element on ties, which is standard practice.

Real-world usage: merge sort's stability and predictable O(n log n) behavior make it the natural choice for external sorting, sorting data too large to fit in memory, which is exactly what the classic Unix sort command does with big files and what the shuffle-and-sort phase in distributed data processing systems like Hadoop's MapReduce relies on. When your data lives partly on disk, merge sort's "process chunks, merge results" structure maps directly onto reading and merging sorted chunks from disk.

5. Quicksort: Fast in Practice, Risky in Theory

Quicksort picks one element as a "pivot," then rearranges the array so everything smaller than the pivot ends up on its left and everything larger ends up on its right. Then it recursively does the same thing to each side.

Real-life example: You're sorting a messy pile of exam papers by score and you grab one paper at random as a reference point, say a paper scoring 70. You make two piles: papers scoring less than 70 on your left and papers scoring more than 70 on your right. Then you repeat the exact same trick separately on each pile, picking a new reference paper each time, until every pile has one paper or none left.

Quicksort on [8, 3, 5, 4, 7, 6] -- pick a pivot, split around it, repeat

[8, 3, 5, 4, 7, 6]   pivot = 4 (middle element)
   less than 4: [3]         greater than 4: [8, 5, 7, 6]

   [8, 5, 7, 6]      pivot = 7
      less than 7: [5, 6]      greater than 7: [8]

      [5, 6]         pivot = 6
         less than 6: [5]      greater than 6: []

Putting the pieces back together, smallest to largest:
   [3]  +  4  +  ([5]  +  6  +  [])  +  7  +  [8]
   =  [3, 4, 5, 6, 7, 8]

Notice there's no separate 'merge' step like merge sort has --
once every piece is sorted and placed on the correct side of its
pivot, the whole array is already in order.

import java.util.Arrays;

public class QuickSort {
    static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // Swap
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // Put pivot in its correct position
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
    public static void main(String[] args) {
        int[] arr = {8, 3, 5, 4, 7, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

• Time complexity: best and average case O(n log n), but worst case O(n²).
• Space complexity: O(log n) for the recursion stack in average space and O(n) in the worst case
• Stable: no

When the worst case actually happens: quicksort's O(n²) worst case is not a theoretical footnote you can ignore. It shows up for real whenever the pivot choice consistently produces lopsided splits, most commonly when the pivot is always the first or last element and the input is already sorted (or sorted in reverse). Each split then peels off just one element instead of roughly half the array, turning what should be log n levels of recursion into n levels. This is also, in principle, an attack surface, if an attacker knows exactly how your quicksort picks its pivot and can control the input order, they can hand you an adversarial worst-case input on purpose. It's the same underlying idea as the hash-flooding denial-of-service attacks covered in our Searching Algorithms guide: an algorithm's average case isn't a guarantee if someone else controls what you feed it. This exact risk is why serious sorting libraries pick the pivot randomly or use the median of a few sampled elements, instead of always grabbing the first or last one.

Real-world usage: this worst-case risk is also why the C++ Standard Library's std::sort isn't plain quicksort. It uses an algorithm called introsort, designed by David Musser in 1997, which runs quicksort normally but automatically switches to heap sort if the recursion goes deeper than expected, guaranteeing O(n log n) worst-case behavior no matter what the input looks like, while keeping quicksort's usual speed on typical data.

6. Heap Sort: The Hospital Emergency Room Algorithm

Heap sort first organizes the array into a max-heap, a structure where every parent is larger than its children, so the largest value always sits at the very top. It then repeatedly pulls the top (largest) value out, moves it to the end of the array and re-organizes what's left to restore the heap property.

Real-life example: Think about how a hospital emergency room actually works. Patients aren't treated in the order they arrived. They're treated in order of how urgent their condition is and every time a new patient arrives, the queue re-organizes itself so the most critical patient is always the next one seen. That's exactly what a heap does. It's not fully sorted at every moment, but the single most important item is always instantly accessible at the top.

import java.util.Arrays;

public class HeapSort {
    static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }

    static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);   // build the max-heap
        for (int i = n - 1; i > 0; i--) {                          // repeatedly extract the max
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2};
        heapSort(a);
        System.out.println(Arrays.toString(a));          // [1, 2, 4, 5]

        int[] b = {9, 8, 7, 6, 5, 4};
        heapSort(b);
        System.out.println(Arrays.toString(b));          // [4, 5, 6, 7, 8, 9]
    }
}

• Time complexity: O(n log n) in the best, average and worst case, with no exceptions. This is heap sort's whole selling point. It has the reliability of merge sort without needing merge sort's extra memory.
• Space complexity: O(1), it sorts in place.
• Stable: no, moving elements around the heap can change the relative order of equal values.

When to use it: whenever you need a guaranteed O(n log n) worst case with almost no extra memory and you don't care about stability. This same underlying max-heap structure is also the foundation of priority queues, which show up constantly in real systems: task schedulers that always run the highest-priority job next and pathfinding algorithms like Dijkstra's algorithm, which repeatedly need "give me the closest unvisited node" as fast as possible.

7. Counting Sort: When You Don't Need to Compare at All

Counting sort works by counting how many times each distinct value appears, then using those counts to figure out exactly where every value belongs in the final sorted output. It never compares two elements to each other.

Real-life example: A teacher has 40 exam scores, all whole numbers between 0 and 100 and wants them sorted. Instead of comparing scores pairwise, the teacher just makes a tally: how many students scored 0, how many scored 1 and so on, up to 100. Then reading the tally from 0 to 100 in order and writing out each score exactly as many times as it appeared gives you the fully sorted list, without a single comparison between two students' scores.

import java.util.Arrays;

public class CountingSort {
    static int[] countingSort(int[] arr) {
        if (arr.length == 0) return arr;
        int maxVal = Arrays.stream(arr).max().getAsInt();
        int[] counts = new int[maxVal + 1];
        for (int x : arr) counts[x]++;
        int[] result = new int[arr.length];
        int idx = 0;
        for (int value = 0; value <= maxVal; value++) {
            for (int c = 0; c < counts[value]; c++) result[idx++] = value;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(countingSort(new int[]{5, 1, 4, 2, 1, 5})));    // [1, 1, 2, 4, 5, 5]
        System.out.println(Arrays.toString(countingSort(new int[]{88, 92, 75, 92, 60})));  // [60, 75, 88, 92, 92]
    }
}

• Time complexity: O(n + k), where n is the number of elements and k is the range of possible values.
• Space complexity: O(k) for the counts array.
• Stable: yes, if implemented carefully (a slightly more involved version than the one above, tracking positions rather than just counts, preserves this). This can be noticeably faster than any comparison-based sort, but only when k stays small relative to n. Sorting a million exam scores from 0 to 100 is a great fit. Sorting a million arbitrary 64-bit numbers is not, since k would be astronomically large and the counts array would be impossibly big.

8. Radix Sort: The Algorithm Older Than Computers

Radix sort sorts numbers (or fixed-length strings) digit by digit, starting from the least significant digit, using a stable sort like counting sort at each digit position, until every digit has been processed.

Real-life example and a surprising bit of history: radix sort isn't a modern invention. Herman Hollerith designed a version of it in 1887 for his mechanical tabulating machines, built to process U.S. census data and by 1923, radix-based sorting had become the standard way punch card sorting machines organized physical cards, feeding them through a machine that sorted them one column (digit) at a time. Modern computerized radix sort, using arrays and buckets instead of physical cards, was formalized later, with Harold Seward developing a memory-efficient version at MIT in 1954. The core idea hasn't changed in over a century: sort by the last digit first, then the next and so on, until the whole thing is in order.

import java.util.*;

public class RadixSort {
    static int[] radixSort(int[] arr) {
        if (arr.length == 0) return arr;
        int[] result = arr.clone();
        int maxVal = Arrays.stream(result).max().getAsInt();
        int place = 1;
        while (maxVal / place > 0) {
            List<List<Integer>> buckets = new ArrayList<>();
            for (int b = 0; b < 10; b++) buckets.add(new ArrayList<>());
            for (int num : result) {
                int digit = (num / place) % 10;
                buckets.get(digit).add(num);
            }
            int idx = 0;
            for (List<Integer> bucket : buckets) {
                for (int num : bucket) result[idx++] = num;
            }
            place *= 10;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(radixSort(new int[]{170, 45, 75, 90, 802, 24, 2, 66})));
        // [2, 24, 45, 66, 75, 90, 170, 802]
    }
}

• Time complexity: O(d × (n + k)), where d is the number of digits in the largest number and k is the base being used (usually 10). For fixed-length numbers, d is effectively a constant, which makes this O(n) in practice.
• Space complexity: O(n + k).
• Stable: yes, as long as the sort used at each digit position is stable, which is why counting sort is the standard choice for that inner step.

When to use it: sorting large volumes of fixed-length data like phone numbers, ZIP codes, IDs or dates in a fixed format, where the number of digits is small and known in advance.

9. Bucket Sort: Sorting Mail by Region

Bucket sort distributes elements into a number of "buckets" based on their value range, sorts each bucket individually (often with insertion sort, since buckets are usually small) and then concatenates the buckets in order.

Real-life example: This is exactly how postal sorting works at scale. Mail first gets split into buckets by broad region or ZIP code range and only after that does each regional office do the finer sorting for its own smaller pile. Splitting into buckets first turns one huge sorting problem into many small, cheap ones.

import java.util.*;

public class BucketSort {

    static void bucketSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        // Find minimum and maximum values
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        // Define the size of each bucket
        int bucketSize = 10;
        // Calculate number of buckets
        int bucketCount = (max - min) / bucketSize + 1;
        // Create buckets
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        // Put elements into appropriate buckets
        for (int num : arr) {
            int bucketIndex = (num - min) / bucketSize;
            buckets.get(bucketIndex).add(num);
        }
        // Sort each bucket
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }
        // Combine all buckets back into the original array
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {
            42, 32, 23, 52, 25,
            47, 51, 15, 8
        };
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

• Time complexity: average case O(n + k) when values are spread out reasonably evenly across the buckets, but worst case O(n²) if all the values happen to land in the same bucket, which just turns the whole thing into one big insertion sort.
• Space complexity: O(n + k).

When to use it: data that's roughly uniformly distributed across a known range, like floating-point numbers between 0 and 1.

1. What is the best sorting algorithm?

There isn't one universal answer. Quicksort is usually fastest in practice for general-purpose, in-memory sorting. Merge sort is the safer choice when you need a guaranteed O(n log n) worst case and stability. Most real programming languages actually use a hybrid, like Timsort, rather than picking just one.

2. What is the difference between bubble sort and quicksort?

Bubble sort compares and swaps neighboring elements repeatedly and runs in O(n²) time on average, making it suitable only for very small or educational examples. Quicksort splits the array around a pivot and recurses, running in O(n log n) time on average, which makes it practical for real, large-scale sorting despite having a worse O(n²) worst case.

3. Which sorting algorithm is stable?

Bubble sort, insertion sort, merge sort and radix sort are stable in their standard form. Quicksort, heap sort and standard selection sort are not stable by default, though stable variants of some of them do exist with extra bookkeeping.

4. What is the time complexity of sorting algorithms in general?

Comparison-based sorting algorithms cannot beat O(n log n) in the general case, which is a proven mathematical lower bound, not just an observation. Non-comparison-based algorithms like counting sort and radix sort can do better, O(n + k) or O(d(n + k)), but only under specific conditions on the data, like a small known range of values.

5. Do Python and Java use quicksort or merge sort?

Neither, exactly. Both use Timsort, a hybrid algorithm that combines merge sort's merging strategy with insertion sort's efficiency on small or already-sorted sections of data, specifically tuned for how real-world data actually looks.

6. Why does quicksort have a bad worst case if it's supposed to be fast?

Its speed depends on the pivot splitting the array into two roughly equal halves each time. If the pivot choice is unlucky or predictable and the input happens to be already sorted or specifically crafted, the splits become extremely uneven and the algorithm degrades to O(n²). Randomizing the pivot choice makes this far less likely in practice.

7. How This Guide Was Checked

Every sorting algorithm shown here was written in Java, compiled with javac and actually run across multiple test cases, including empty arrays, single elements, duplicates and already-reverse-sorted input, to confirm each one produces a correct result. The stability example, built around a Java record and Comparator.comparing(), was run and its output checked line by line. Both historical stories, the Timsort bug and radix sort's punch-card origins, were checked against the original research and primary references rather than secondhand summaries.