Sorting algorithms explained: bubble, merge and quick sort

Sorting algorithms put items in a defined order, and they differ in speed, memory use and stability. Bubble, selection and insertion sort take O(n^2) time in the worst case. Merge sort takes O(n log n) in every case but needs O(n) extra space. Quicksort averages O(n log n) and has an O(n^2) worst case. Python and JavaScript sort stably, so equal items keep their input order.

What is a sorting algorithm, and what does stable mean?

A sorting algorithm rearranges a list into ascending or descending order. Most are comparison sorts: they decide where an item goes only by asking whether one item is smaller than another. Any comparison sort needs about N lg N compares in the worst case to sort N items, and Princeton's Algorithms text shows merge sort reaches that bound.

A sort is stable if it does not change the relative order of elements that compare equal. The Python documentation uses exactly this definition and adds that stability is useful for sorting in several passes, such as by department and then by salary grade.

The sample below sorts four hypothetical people by city. Python's built-in sort keeps Asha ahead of Chitra, who share a city. A swap-based selection sort moves them apart.

people = [("Asha", "Pune"), ("Bala", "Delhi"), ("Chitra", "Pune"), ("Dev", "Delhi")]
print([name for name, city in sorted(people, key=lambda p: p[1])])

def selection_sort_by_city(a):
    a = a[:]
    for i in range(len(a) - 1):
        m = min(range(i, len(a)), key=lambda j: a[j][1])
        a[i], a[m] = a[m], a[i]
    return a

print([name for name, city in selection_sort_by_city(people)])

['Bala', 'Dev', 'Asha', 'Chitra']
['Bala', 'Dev', 'Chitra', 'Asha']

How do bubble, selection and insertion sort work?

Bubble sort compares each adjacent pair, swaps the pair if it is out of order, and repeats the pass until no swap happens, according to NIST's Dictionary of Algorithms and Data Structures. Each pass carries the largest remaining item to the end. Stopping when a pass makes no swap is what lets bubble sort finish in about n steps on data that is already sorted.

Selection sort scans the unsorted part for the smallest item and swaps it into the next position. Insertion sort takes the next item and slides it left past larger items, the way most people arrange playing cards. The table traces all three on the same five-element array, [5, 2, 4, 1, 3].

The bubble sort column comes from this code, which prints the array after each pass.

def bubble_sort(a):
    a = a[:]
    n = len(a)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        print("after pass", n - end, a)
        if not swapped:
            break
    return a

print(bubble_sort([5, 2, 4, 1, 3]))

after pass 1 [2, 4, 1, 3, 5]
after pass 2 [2, 1, 3, 4, 5]
after pass 3 [1, 2, 3, 4, 5]
after pass 4 [1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

The three share a cost profile. Selection sort uses about n^2/2 compares and n exchanges whatever the input. Insertion sort uses N-1 compares in the best case and about N^2/2 in the worst, and the Princeton text shows its number of exchanges equals the number of inversions, the out-of-order pairs, in the array. That is why insertion sort is cheap on nearly sorted data.

How does merge sort work?

Merge sort splits the items into two groups, recursively sorts each group and merges the two sorted halves into one sorted sequence. NIST gives its run time as Theta(n log n), and Princeton's text adds that it needs extra space proportional to N, because merging copies items into an auxiliary array.

On [5, 2, 4, 1, 3] the merges run in this order: [5] with [2] gives [2, 5]; [1] with [3] gives [1, 3]; [4] with [1, 3] gives [1, 3, 4]; and [2, 5] with [1, 3, 4] gives [1, 2, 3, 4, 5]. The comparison left[i] <= right[j] in the code takes the left item on a tie, which is what makes the sort stable.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= keeps equal keys in original order
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

print(merge_sort([5, 2, 4, 1, 3]))

[1, 2, 3, 4, 5]

How does quicksort work, and why is its worst case O(n^2)?

Quicksort picks one element as the pivot, partitions the rest into items smaller and larger than the pivot, and recursively sorts the two partitions. NIST lists it as an in-place sort. With the last element as pivot, one partition of [5, 2, 4, 1, 3] uses 3 as the pivot and leaves [2, 1, 3, 5, 4], with the pivot already in its final position at index 2.

The worst case arrives when every pivot is the smallest or largest remaining item. One partition then holds everything else and the other is empty, so the work is (n-1) + (n-2) + ... + 1, which is n(n-1)/2 compares. A fixed last-element pivot does this on input that is already sorted, a common case in real data. Princeton's text notes that randomly shuffling the array first makes the quadratic case very unlikely, with about 2 N ln N compares on average.

def quicksort(a, lo, hi, counter):
    if lo >= hi:
        return
    pivot, i = a[hi], lo
    for j in range(lo, hi):
        counter[0] += 1
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    quicksort(a, lo, i - 1, counter)
    quicksort(a, i + 1, hi, counter)

The counting driver below calls that function on an already sorted list and on a shuffled one.

import random

def comparisons(data):
    a, counter = data[:], [0]
    quicksort(a, 0, len(a) - 1, counter)
    assert a == sorted(data)
    return counter[0]

n = 500
shuffled = list(range(n))
random.seed(1)
random.shuffle(shuffled)
print("already sorted:", comparisons(list(range(n))))
print("shuffled      :", comparisons(shuffled))
print("n(n-1)/2      :", n * (n - 1) // 2)

already sorted: 124750
shuffled      : 4751
n(n-1)/2      : 124750

Which sorting algorithm is the fastest?

No single algorithm wins on every input. Princeton's text calls quicksort the fastest general-purpose sort in most practical situations, and says merge sort may be the better pick when stability matters and memory is available. The table gives the standard figures.

Bubble sort figures follow NIST's note that it approaches linear time on nearly ordered data, and the other rows follow the Princeton summary of in-place and stable sorts. The quicksort space figure is the recursion depth, which Princeton gives as logarithmic with high probability.

Counting the compares on a real array makes the gap concrete. The next table shows the comparisons each algorithm used on 500 items, from the code above and its siblings.

One exception to the n log n floor exists. Counting sort does not compare items at all, and the Competitive Programmer's Handbook shows it sorts in O(n) time when the values are integers from 0 to c with c itself O(n). It suits small integer ranges and little else.

Which sorting method do Python, Java and other languages use?

Python's list.sort() and sorted() use Timsort, an adaptive, stable natural mergesort written by Tim Peters. His design notes say it can need as few as N-1 comparisons on partly ordered input and a temporary array of up to N/2 pointers. The Python documentation states the sort is stable.

JavaScript's Array.prototype.sort has been required to be stable since ECMAScript 2019. V8, the engine in Chrome, moved from quicksort to Timsort in V8 v7.0 and Chrome 70, and stability was one reason for the move. Without a comparison function JavaScript sorts as strings, so [1, 200, 40, 5] stays [1, 200, 40, 5].

const nums = [1, 200, 40, 5];
console.log(nums.slice().sort());
console.log(nums.slice().sort((a, b) => a - b));

[ 1, 200, 40, 5 ]
[ 1, 5, 40, 200 ]

Java sorts primitives with a fast unstable algorithm because two equal ints cannot be told apart, and sorts objects stably. In C++ the standard has required O(N log N) comparisons for std::sort since a defect report, LWG 713, so a plain quicksort alone no longer qualifies, and introsort is the usual choice.

What are the limits and common mistakes?

Hand-written sorts are for learning. Production code should call the library sort, which is tested and tuned, and the main remaining decision is whether stability matters. Several mistakes recur:

• Using bubble or selection sort on large inputs, where the quadratic compare count grows fast.
• Forgetting that a swap-based selection sort and a plain quicksort are not stable.
• Passing no comparator to JavaScript's sort() on numbers.
• Choosing a fixed first or last pivot for quicksort on data that may arrive sorted.
• Reaching for merge sort without budgeting its O(n) extra space.

Big-O figures also hide constants. The comparison counts above ignore memory access patterns, and a quadratic algorithm can win on very small arrays, which is why V8's Timsort extends short runs with insertion sort. How complexity is measured is covered in time complexity and Big O notation for beginners, and a sorted array is also what makes binary search possible. The wider set of foundations appears in Data Structures and Algorithms explained with examples.

Where does sorting fit in AI and machine learning study?

Sorting is the first step in several everyday data tasks, such as ranking items and finding duplicates, which Princeton's text solves in linearithmic time by sorting first. Certification in Artificial Intelligence and Machine Learning is an online programme from Vishlesan i-Hub, IIT Patna, delivered on Masai's online platform, that covers Python, machine learning, deep learning, generative AI and LLMs, agentic systems and deploying models to production.

Its first module, Core Programming & Analytical Foundations, is where Python programming and SQL queries sit, and the later modules include Predictive Modelling & Machine Learning Systems. Details are on the Certification in Artificial Intelligence and Machine Learning page.

Frequently asked questions

Which sorting algorithm is the fastest?

None is fastest on every input. For general-purpose comparison sorting, quicksort is usually quickest in practice according to Princeton's Algorithms text, merge sort and Timsort give an O(n log n) worst case, and insertion sort wins on tiny or nearly sorted arrays. Counting sort runs in O(n) for small integer ranges.

What is a stable sorting algorithm?

A stable sorting algorithm keeps the original relative order of items that compare equal. Merge sort and insertion sort are stable, while selection sort, quicksort and heapsort are not in their usual forms. Stability matters when sorting records by one field after another, such as city and then name.

Why is quicksort worst case O(n squared)?

Quicksort goes quadratic when each pivot is the smallest or largest item left, because one partition then holds everything else. The compares add up to (n-1) + (n-2) + ... + 1, which is n(n-1)/2. A fixed last-element pivot on sorted input triggers this, and random pivots or shuffling make it very unlikely.

Which sorting algorithm does Python use?

Python uses Timsort, an adaptive, stable natural mergesort, for both list.sort() and sorted(). It finds runs that are already ordered and merges them, so sorted or partly sorted input costs far fewer comparisons than random input. The Python documentation states the sort is stable.

Is merge sort better than quicksort?

Neither is better on every measure. Merge sort has an O(n log n) worst case and is stable but needs O(n) extra space. Quicksort sorts in place with logarithmic extra space and is often faster in practice, but it is not stable and has an O(n^2) worst case unless pivots are chosen carefully.

Which sorting algorithm is best for nearly sorted data?

Insertion sort and Timsort handle nearly sorted data best. Insertion sort uses a number of exchanges equal to the number of out-of-order pairs, so few swaps are needed. Timsort detects existing ordered runs and can finish in about n comparisons on already sorted input.

Next step

To keep building the Python and analytical base that data and AI work relies on, look at the Certification in Artificial Intelligence and Machine Learning programme from Vishlesan i-Hub, IIT Patna. After sorting, the natural next topic is searching: see how binary search explained with code halves a sorted list at every step.