Sorting Algorithms Comparison

You have learned a bunch of sorting algorithms by now. Bubble, selection, insertion, merge, quick, heap, and a few more. So a real question hits you in an interview or in your own code. Which one do I actually pick? They all sort the same list. But they are not the same speed. They do not use the same memory. Some keep equal items in their original order. Some do not. This page is your one-stop comparison. Keep it open like a cheat sheet.

🎯 The Problem This Page Solves

Here is the pain. You sit down to write code that sorts something. Maybe it is a list of names. Maybe it is a million numbers. You freeze. You know five sorting methods and you have no idea which one fits.

The fix is simple. You do not memorize code. You memorize a small set of facts about each sort. How fast it is. How much extra memory it eats. Whether it is stable. Stable means equal items stay in the same order they came in. Once you know these facts, picking the right sort takes a few seconds.

📚 First, Some Words You Must Know

Before the big table, let us lock down these ideas. Everything below leans on them.

Time complexity. This is how the running time grows as the list gets bigger. We write it with Big O. O(n) means the time grows in a straight line with the size. O(n log n) is a bit more than that. O(n²) means if you double the list, the time goes up four times. That last one gets slow fast.

Stability. Say you sort a list of students by marks. Two students both have 90 marks. A stable sort keeps them in the same order they were before. An unstable sort might swap them. This matters when you sort by one thing after you already sorted by another.

📊 The Big Comparison Table

Here is the heart of the page. Every common sort, side by side. Read across each row.

Two of those rows have a letter k in them. That needs a word. For counting sort, k is the size of the range of your numbers. So if your numbers go from 0 to 100, k is about 100. For radix sort, k is the number of digits in the biggest number. These sorts do not compare items against each other. So the usual O(n log n) limit does not apply to them.

🗂️ Notes And When To Use Each

The table gives you the numbers. This part gives you the feel. Here is a short note on each one and when it actually makes sense. The key thing to watch is whether a sort works in place, which means it sorts without asking for much extra memory.

🧭 So Which One Do I Pick?

Let me make this very simple. In real life you rarely write a sort by hand. You call the one built into your language. It is already very good. But you still need to know what fits. This helps in interviews. It also helps for the cases where the built-in is not enough.

Here is the quick guide:

• Small list, or almost sorted already? Reach for insertion sort. It is tiny and it beats the fancy ones when n is small.
• General all-purpose sorting? Use quick sort or merge sort. Or honestly, just call your language’s built-in sort. It already uses these inside.
• Need a guaranteed worst case, no surprises? Use merge sort or heap sort. Both stay O(n log n) even on the nastiest input.
• Need equal items to keep their order (stable)? Use merge sort, insertion sort, or counting sort. Avoid quick sort and heap sort here.
• Sorting integers in a small range, like ages 0 to 120? Use counting sort. It skips comparing and runs in O(n + k).
• Sorting integers with a few digits, or fixed-length IDs? Use radix sort.
• Memory is very tight? Heap sort sorts in place with O(1) extra space and never goes quadratic.

Here is a tiny taste of calling the built-in sort in each language. You almost never need to hand-write a sort for everyday work.

#include <stdio.h>
#include <stdlib.h>

// Comparator: tells qsort how to order two integers
int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main(void) {
    int arr[] = {5, 2, 9, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    // C's standard library sort
    qsort(arr, n, sizeof(int), cmp);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

1 2 5 7 9

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = {5, 2, 9, 1, 7};

    // C++ standard library sort (introsort inside)
    sort(arr.begin(), arr.end());

    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

1 2 5 7 9

import java.util.Arrays;

public class BuiltinSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7};

        // Java's built-in sort
        Arrays.sort(arr);

        System.out.println(Arrays.toString(arr));
    }
}

[1, 2, 5, 7, 9]

def sort_demo():
    arr = [5, 2, 9, 1, 7]

    # Python's built-in sort (Timsort inside, stable)
    arr.sort()

    print(arr)

sort_demo()

[1, 2, 5, 7, 9]

function sortDemo() {
  const arr = [5, 2, 9, 1, 7];

  // Numeric compare, else JS sorts as text
  arr.sort((a, b) => a - b);

  console.log(arr);
}

sortDemo();

[ 1, 2, 5, 7, 9 ]

⚠️ Common Mistakes To Avoid

A few traps catch students again and again. Watch for these. The most common one is to trust the average case and forget the worst case.

• Thinking quick sort is always O(n log n). Its worst case is O(n²) when the pivot is picked badly, like on an already sorted list with a naive pivot.
• Forgetting that merge sort needs extra O(n) memory. On very tight memory, that can be a problem.
• Using counting sort when the number range is huge. If your numbers go up to a billion, counting sort needs a billion-sized helper. That is a disaster.
• Picking an unstable sort when the order of equal items matters. If you sorted by name and then sort by age, an unstable sort can scramble the name order.
• Writing your own sort for normal work. The built-in sort is tested and fast. Use it unless you have a strong reason not to.

🧩 What You’ve Learned

• ✅ Every common sort compared by best, average, worst time, space, and stability in one table.
• ✅ What stability means and why it matters when you sort by one key after another.
• ✅ That O(n log n) sorts crush O(n²) sorts on big data, and how much faster they really are.
• ✅ When to pick each sort: insertion for small or near-sorted, quick or merge for general use, counting or radix for small-range integers, heap when memory is tight.
• ✅ That your language’s built-in sort already uses these ideas, and the JavaScript numeric-compare trap.

🚀 What’s Next?

• Quick Sort
• Big O Cheat Sheet