Sorting

Sorting is one of the most studied problems in computer science. Not because arranging numbers in order is interesting by itself - but because sorted data makes every other problem easier.

This guide covers the theory behind sorting, why so many algorithms exist, and the three foundational sorting algorithms every developer must know.

What is Sorting?

Sorting means rearranging elements into a specific order.

Most common:

• Ascending: small to large - [1, 3, 5, 7]
• Descending: large to small - [7, 5, 3, 1]

Sorting does not change the values - only the positions.

Input:  [7, 3, 5, 1]
Output: [1, 3, 5, 7]

Why Does Sorting Even Matter?

If sorting was just about making data look neat, it would not be important. Sorting exists because it unlocks faster algorithms on the data.

Faster Searching

Unsorted data:

[40, 10, 30, 20]

Finding 30 means checking every element - O(n) time.

Sorted data:

[10, 20, 30, 40]

Now you can use Binary Search - O(log n) time.

That is a massive difference for large datasets.

Simplifies Many Problems

After sorting, problems like these become much easier:

• Find duplicates
• Find the k-th smallest element
• Merge two datasets
• Two-pointer problems
• Interval problems

That is why so many DSA solutions start with: “First, sort the array…”

Two Types of Sorting Algorithms

Comparison-Based Sorting

These algorithms compare pairs of elements to decide their order.

Is 5 less than 7? -> yes -> keep this order

The Mathematical Limit: No comparison-based sorting algorithm can ever be faster than O(n log n) in the worst case. This is proven mathematically.

Why? Because every comparison gives only 1 bit of information (yes/no), and sorting n elements requires at least log₂(n!) bits - which works out to n log n.

So Merge Sort, Quick Sort, and Heap Sort are all theoretically as good as it gets for comparison-based sorting.

Non-Comparison-Based Sorting

These algorithms do not compare elements. Instead they:

• Use element values as positions
• Count occurrences
• Work on digit by digit

Examples: Counting Sort, Radix Sort, Bucket Sort.

They can beat O(n log n) - sometimes O(n) - but only when:

• Values are integers
• The range of values is limited and known
• Data has special structure

Tip

If an interviewer asks “can we sort faster than O(n log n)?”, the correct answer is: not with comparison-based sorting, but yes with non-comparison methods under specific conditions.

Why Do So Many Sorting Algorithms Exist?

This is one of the most common interview theory questions. The answer is: real-world constraints vary.

There is no single best sorting algorithm. The best choice depends on:

Input Size

Size	Approach
Small (< 20 elements)	Simple algorithms (Insertion Sort)
Large	Efficient algorithms (Merge Sort, Quick Sort)

Input Nature

Data State	Effect on Algorithms
Already sorted	Insertion Sort becomes O(n)
Reverse sorted	Some algorithms hit their worst case
Random	Average-case behavior matters

Memory Constraints

Situation	Best Choice
Limited RAM	In-place sorting (O(1) extra space)
Memory available	Out-of-place sorting (easier, often stable)

Stability Requirement

Need	Use
Order of equal elements must be preserved	Stable sort
Order does not matter	Any sort

Data Range

Data	Best Type
Small integers with known range	Non-comparison (Counting Sort)
Large values, strings, objects	Comparison sort

Note

The correct interview answer to “which sort would you use?” is never a direct answer. First ask about input size, memory, stability, and data range. Then conclude.

Stable vs Unstable Sorting

This is very important and often tested.

What Does Stable Mean?

A sort is stable if equal elements keep their original relative order after sorting.

Example - sorting by the number:

Input:  [(A, 5), (B, 5), (C, 3)]
         index 0  index 1  index 2

Both A and B have the value 5. After sorting by number:

Stable result:

[(C, 3), (A, 5), (B, 5)]

A still comes before B - same as the original.

Unstable result:

[(C, 3), (B, 5), (A, 5)]

B and A swapped - original relative order was lost.

Why Stability Matters

Imagine sorting a list of employees first by name (alphabetically), then by salary.

If the second sort (by salary) is stable, employees with the same salary keep their alphabetical order from the first sort. If it is unstable, the name ordering is destroyed.

This matters whenever you are sorting objects with multiple fields.

Which Algorithms Are Stable?

Algorithm	Stable?
Bubble Sort	Yes
Insertion Sort	Yes
Merge Sort	Yes
Selection Sort	No
Quick Sort	No (default)
Heap Sort	No

In-Place vs Out-of-Place Sorting

In-Place Sorting

The algorithm sorts the array using the same array - no extra array is created.

Extra space = O(1)

[4, 2, 1, 3]
      ↕ swaps happen inside the same array
[1, 2, 3, 4]

Pros: Memory efficient. Cons: Harder to make stable.

Out-of-Place Sorting

The algorithm uses a separate array to build the sorted result.

Extra space = O(n)

Original: [4, 2, 1, 3]
Helper:   [1, 2, 3, 4]  ← built separately

Pros: Easier to write, easier to make stable. Cons: Uses more memory.

When to Choose

Condition	Choice
Memory is tight	In-place
Stability is required	Out-of-place (usually easier)
Large data, memory available	Either, depending on algorithm

Adaptive Sorting

An algorithm is adaptive if it runs faster when the input is already partially sorted.

Nearly sorted: [1, 2, 3, 4, 6, 5]

An adaptive algorithm recognizes this and does less work.

• Insertion Sort is adaptive - O(n) on already sorted data
• Selection Sort is NOT adaptive - always O(n²) regardless

Adaptive algorithms are useful in real-time systems where data keeps coming in mostly sorted.

Internal vs External Sorting

Internal Sorting

The entire data fits in RAM. All algorithms in this guide are internal sorting.

External Sorting

The data is too large for RAM - it lives on disk. The algorithm must minimize disk reads and writes, which are much slower than memory access.

Used in databases and file systems.

The Three Basic Sorting Algorithms

Every developer must know these three. They are slow for large data but fundamental - and they appear in interviews constantly.

Bubble Sort

The Core Idea

Compare two neighboring elements at a time. If they are in the wrong order, swap them. Keep doing this until nothing swaps.

The largest element “bubbles up” to the end with each pass - that is where the name comes from.

Step-by-Step Example

Array: [5, 1, 4, 2]

Pass 1 - compare neighbors left to right:

(5, 1) -> wrong order -> swap -> [1, 5, 4, 2]
(5, 4) -> wrong order -> swap -> [1, 4, 5, 2]
(5, 2) -> wrong order -> swap -> [1, 4, 2, 5]

After pass 1: 5 is at the end - its correct place.

Pass 2:

(1, 4) -> correct order -> no swap
(4, 2) -> wrong order  -> swap -> [1, 2, 4, 5]

After pass 2: 4 and 5 are in place.

Pass 3:

[1, 2, 4, 5] -> no swaps needed -> done

Code

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):  # last i elements already sorted
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        if not swapped:  # optimization - stop early if already sorted
            break

The swapped flag is the optimization that makes best case O(n) - if no swaps happen in a pass, the array is sorted and we stop early.

Complexity

Case	Time	Why
Best	O(n)	Already sorted - no swaps, one pass
Average	O(n²)	Most elements need moving
Worst	O(n²)	Reverse sorted

Space: O(1) - in-place. Stable: Yes - equal elements never swap.

Selection Sort

The Core Idea

Find the smallest element in the unsorted portion. Put it at the front. Repeat for the rest.

Instead of many swaps like Bubble Sort, Selection Sort does exactly one swap per pass.

Step-by-Step Example

Array: [5, 1, 4, 2]

Pass 1 - find minimum in whole array:

Minimum is 1 (at index 1)
Swap with index 0 -> [1, 5, 4, 2]

Pass 2 - find minimum in remaining [5, 4, 2]:

Minimum is 2 (at index 3)
Swap with index 1 -> [1, 2, 4, 5]

Pass 3 - remaining [4, 5] already sorted.

[1, 2, 4, 5] ✓

Code

def selection_sort(arr):
    n = len(arr)

    for i in range(n):
        min_index = i  # assume current position is minimum

        # find the actual minimum in the rest of the array
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # swap minimum into correct position
        arr[i], arr[min_index] = arr[min_index], arr[i]

Complexity

Case	Time	Why
Best	O(n²)	Always scans remaining elements
Average	O(n²)	Same
Worst	O(n²)	Same

Space: O(1) - in-place. Stable: No - swapping can change relative order of equal elements. Adaptive: No - always O(n²) regardless of input.

Tip

Selection Sort is useful when swap cost is very high - it does the minimum number of swaps (exactly n-1 swaps total). In scenarios where writing to memory is expensive, this matters.

Insertion Sort

The Core Idea

Think about how you sort playing cards in your hand. You pick one card, find where it fits among the cards already in your hand, and slide it in.

That is exactly Insertion Sort. Take one element, and insert it into the correct position among the already-sorted portion.

Step-by-Step Example

Array: [5, 1, 4, 2]

Start:    [5]         | 1  4  2   (sorted | unsorted)
Step 2:   [1, 5]      | 4  2      (1 inserted before 5)
Step 3:   [1, 4, 5]   | 2         (4 inserted between 1 and 5)
Step 4:   [1, 2, 4, 5]            (2 inserted between 1 and 4)

Code

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        key = arr[i]      # the element we want to insert
        j = i - 1

        # shift elements right to make space for key
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key  # insert key in correct position

Complexity

Case	Time	Why
Best	O(n)	Already sorted - no shifting needed
Average	O(n²)	Elements need shifting
Worst	O(n²)	Reverse sorted - max shifting

Space: O(1) - in-place. Stable: Yes. Adaptive: Yes - fastest of the three on nearly sorted data.

Note

Python’s built-in sort() uses TimSort, which is a hybrid of Merge Sort and Insertion Sort. It uses Insertion Sort for small chunks because it is very fast on small or nearly-sorted data.

Side-by-Side Comparison

Algorithm	Best	Average	Worst	Space	Stable	Adaptive
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes

When to Use Which

Situation	Best Choice
Learning / teaching	Bubble Sort
Swaps are expensive	Selection Sort
Data is nearly sorted	Insertion Sort
Need a stable sort	Bubble or Insertion
Any real production code	Merge Sort or Quick Sort (next topic)

The Interview Framework - How to Answer “Which Sort?”

Never answer sorting algorithm questions directly. Use this structure:

1. Ask about input size - small or large?

2. Ask about memory - do we have extra space available?

3. Ask about stability - do equal elements need to keep their order?

4. Ask about data distribution - is it random, nearly sorted, or reverse sorted?

5. Ask about data range - are values integers in a known range?

6. Now give your answer - based on the constraints, pick the right algorithm and explain why.

Quick Reference

Bubble Sort

Compares neighbors, swaps if wrong order. O(n²) average. Stable. Good for learning and nearly sorted data with the swapped optimization.

Selection Sort

Finds minimum, swaps once per pass. O(n²) always. Not stable, not adaptive. Use when swaps are expensive.

Insertion Sort

Inserts one element at a time into sorted portion. O(n) best case. Stable and adaptive. Best for small or nearly sorted data.

Stability

Stable = equal elements keep original order. Bubble and Insertion are stable. Selection is not.

In-Place

All three use O(1) extra space - no extra array needed.

No Single Best

The best sorting algorithm depends on input size, memory, stability needs, and data distribution. Always ask first.

Summary

Theory

• Sorting makes searching O(log n) instead of O(n)
• Comparison-based sorting cannot beat O(n log n) - mathematical law
• Non-comparison sorting can be faster but needs special data conditions
• No single best algorithm - always choose based on constraints

The Three Algorithms

• Bubble Sort - swap neighbors, large values bubble to end, O(n²)
• Selection Sort - find min, put in place, one swap per pass, O(n²)
• Insertion Sort - insert into sorted portion, like playing cards, O(n) best case
• All three are O(1) space (in-place)

Key Properties

• Stable: Bubble Sort, Insertion Sort
• Adaptive: Bubble Sort (with flag), Insertion Sort
• Fewest swaps: Selection Sort (exactly n-1)
• Best for nearly sorted: Insertion Sort
• Production code: Use Python’s built-in sort() - it uses TimSort

Tip

The most common interview mistake is jumping straight to “I would use Quick Sort” or “Merge Sort” without asking about the constraints. Always establish the problem requirements first, then justify your choice.