Autocoder

Sorting algorithm interview questions with worked solutions

Last updated 2026-11-19

Interviewers ask about sorting for two reasons: to see whether you can write a standard algorithm correctly, and to see whether you understand its trade-offs. You are expected to know the time and space complexity of each, whether it is stable, and when a non-comparison sort beats O(n log n).

This page works through the algorithms you may be asked to write from memory, then the applied problems where sorting is the trick: custom comparators, selection without a full sort and counting inversions. For what to do with sorted data afterwards, see binary search questions and two pointers questions.

Questions11, easy to hard
LanguagesPython and Java
Also coversStability, quickselect, comparators

Comparison table to remember

Bubble, insertion and selection sort are O(n^2) in the worst case. Merge sort and heap sort are O(n log n) worst case; quick sort is O(n log n) on average but O(n^2) in the worst case. Counting sort is O(n + k) for integers in a range of size k.

A sort is stable if equal elements keep their original order. Merge sort and insertion sort are stable; quick sort and heap sort usually are not. Stability matters when sorting records by several keys in turn.

Library sorts you should know

Python sorted and list.sort use Timsort, a stable hybrid of merge and insertion sort. Java Arrays.sort on primitives uses dual-pivot quick sort, while on objects it uses a stable merge-based Timsort. In an interview, say you would call the library sort unless the question is specifically about implementing one.

Sorting algorithm interview questions with worked solutions: questions with worked answers

  1. 1

    Write bubble sort with an early exit.

    easy

    Repeatedly pass through the array, swapping adjacent elements that are out of order. After pass i the largest i elements are in place, so the inner loop shortens. If a full pass makes no swap, the array is sorted and you can stop, which makes the best case O(n). Time O(n^2) worst and average, O(n) best with the early exit; space O(1); stable.. Edge cases: already sorted input, a single element, all equal elements.

    python
    def bubble_sort(a):
        n = len(a)
        for i in range(n - 1):
            swapped = False
            for j in range(n - 1 - i):
                if a[j] > a[j + 1]:
                    a[j], a[j + 1] = a[j + 1], a[j]
                    swapped = True
            if not swapped:
                break
    java
    import java.util.*;
    
    class Solution {
        static void bubbleSort(int[] a) {
            for (int i = 0; i < a.length - 1; i++) {
                boolean swapped = false;
                for (int j = 0; j < a.length - 1 - i; j++) {
                    if (a[j] > a[j + 1]) {
                        int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                        swapped = true;
                    }
                }
                if (!swapped) break;
            }
        }
    }
  2. 2

    Write insertion sort and say when it is the best choice.

    easy

    Treat the left part as sorted. Take the next element as a key, shift larger elements one place right and drop the key into the gap. It is the fastest simple sort for small arrays or nearly sorted data, which is why hybrid sorts use it for tiny partitions. Time O(n^2) worst, O(n) best; space O(1); stable.. Edge cases: sorted input, reverse-sorted input (worst), duplicates (stable if shifting uses > not >=).

    python
    def insertion_sort(a):
        for i in range(1, len(a)):
            key = a[i]
            j = i - 1
            while j >= 0 and a[j] > key:
                a[j + 1] = a[j]
                j -= 1
            a[j + 1] = key
    java
    import java.util.*;
    
    class Solution {
        static void insertionSort(int[] a) {
            for (int i = 1; i < a.length; i++) {
                int key = a[i], j = i - 1;
                while (j >= 0 && a[j] > key) {
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = key;
            }
        }
    }
  3. 3

    Implement merge sort.

    medium

    Split the array in half, sort each half recursively and merge the two sorted halves. Taking from the left half when values are equal (<=) keeps the sort stable. The merge step needs a temporary buffer, so extra space is O(n). The recursion depth is log n. Time O(n log n) in all cases, space O(n); stable.. Edge cases: length 0 or 1, many duplicates, already sorted input.

    python
    def merge_sort(a):
        if len(a) <= 1:
            return a
        m = len(a) // 2
        left, right = merge_sort(a[:m]), merge_sort(a[m:])
        i = j = 0
        out = []
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                out.append(left[i])
                i += 1
            else:
                out.append(right[j])
                j += 1
        out.extend(left[i:])
        out.extend(right[j:])
        return out
    java
    import java.util.*;
    
    class Solution {
        static void mergeSort(int[] a, int lo, int hi, int[] t) {
            if (hi - lo < 2) return;
            int m = (lo + hi) >>> 1;
            mergeSort(a, lo, m, t);
            mergeSort(a, m, hi, t);
            int i = lo, j = m, k = lo;
            while (i < m && j < hi) t[k++] = a[i] <= a[j] ? a[i++] : a[j++];
            while (i < m) t[k++] = a[i++];
            while (j < hi) t[k++] = a[j++];
            for (k = lo; k < hi; k++) a[k] = t[k];
        }
        // call: mergeSort(a, 0, a.length, new int[a.length]);
    }
  4. 4

    Implement quick sort and explain how to avoid its worst case.

    medium

    Pick a pivot, partition so smaller elements go left and the rest right, then recurse on both sides. Choosing the last element on sorted input gives O(n^2); a random pivot makes that unlikely. With many equal values, Lomuto partitioning also degrades, so use three-way partitioning if duplicates are common. Time O(n log n) average, O(n^2) worst; space O(log n) recursion; not stable.. Edge cases: sorted input, all equal elements, two elements.

    python
    import random
    
    def quick_sort(a, lo=0, hi=None):
        if hi is None:
            hi = len(a) - 1
        if lo >= hi:
            return
        p = random.randint(lo, hi)
        a[p], a[hi] = a[hi], a[p]
        pivot, i = a[hi], lo
        for j in range(lo, hi):
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        quick_sort(a, lo, i - 1)
        quick_sort(a, i + 1, hi)
    java
    import java.util.*;
    
    class Solution {
        static final Random RND = new Random();
    
        static void quickSort(int[] a, int lo, int hi) {
            if (lo >= hi) return;
            int p = lo + RND.nextInt(hi - lo + 1);
            int t = a[p]; a[p] = a[hi]; a[hi] = t;
            int pivot = a[hi], i = lo;
            for (int j = lo; j < hi; j++) {
                if (a[j] < pivot) { t = a[i]; a[i] = a[j]; a[j] = t; i++; }
            }
            t = a[i]; a[i] = a[hi]; a[hi] = t;
            quickSort(a, lo, i - 1);
            quickSort(a, i + 1, hi);
        }
    }
  5. 5

    Implement heap sort.

    medium

    Build a max-heap in place by sifting down from the last parent to the root. Then repeatedly swap the root (the maximum) with the last element of the heap, shrink the heap by one and sift down the new root. The array ends up sorted ascending without extra memory. Time O(n log n) always, space O(1); not stable.. Edge cases: length 0 or 1, duplicates, already sorted input.

    python
    def heap_sort(a):
        n = len(a)
        def sift(i, size):
            while True:
                l, r, m = 2 * i + 1, 2 * i + 2, i
                if l < size and a[l] > a[m]:
                    m = l
                if r < size and a[r] > a[m]:
                    m = r
                if m == i:
                    return
                a[i], a[m] = a[m], a[i]
                i = m
        for i in range(n // 2 - 1, -1, -1):
            sift(i, n)
        for end in range(n - 1, 0, -1):
            a[0], a[end] = a[end], a[0]
            sift(0, end)
    java
    import java.util.*;
    
    class Solution {
        static void heapSort(int[] a) {
            int n = a.length;
            for (int i = n / 2 - 1; i >= 0; i--) sift(a, i, n);
            for (int end = n - 1; end > 0; end--) {
                int t = a[0]; a[0] = a[end]; a[end] = t;
                sift(a, 0, end);
            }
        }
        static void sift(int[] a, int i, int size) {
            while (true) {
                int l = 2 * i + 1, r = l + 1, m = i;
                if (l < size && a[l] > a[m]) m = l;
                if (r < size && a[r] > a[m]) m = r;
                if (m == i) return;
                int t = a[i]; a[i] = a[m]; a[m] = t;
                i = m;
            }
        }
    }
  6. 6

    Counting sort: sort non-negative integers in linear time.

    medium

    Count how often each value occurs in an array of size max + 1, then write each value back that many times. It beats comparison sorts when the value range k is small compared with n. The simple version here is not stable for records; the stable version uses prefix sums of the counts. Time O(n + k), space O(k).. Edge cases: empty array, a large maximum value (memory blow-up), all equal values.

    python
    def counting_sort(a):
        if not a:
            return a
        cnt = [0] * (max(a) + 1)
        for x in a:
            cnt[x] += 1
        out = []
        for v, c in enumerate(cnt):
            out.extend([v] * c)
        return out
    java
    import java.util.*;
    
    class Solution {
        static int[] countingSort(int[] a) {
            if (a.length == 0) return a;
            int max = 0;
            for (int x : a) max = Math.max(max, x);
            int[] cnt = new int[max + 1];
            for (int x : a) cnt[x]++;
            int[] out = new int[a.length];
            int k = 0;
            for (int v = 0; v <= max; v++)
                while (cnt[v]-- > 0) out[k++] = v;
            return out;
        }
    }
  7. 7

    Largest number: arrange non-negative integers to form the largest possible number.

    medium

    Sort as strings with a custom comparator: x comes before y if x+y is greater than y+x as text. For 3 and 30, "330" beats "303", so 3 goes first. Join the result; if the first item is "0", the answer is "0". Time O(n log n * L) for strings of length L, space O(n).. Edge cases: all zeroes (return "0", not "000"), single number, numbers sharing prefixes like 34 and 3.

    python
    from functools import cmp_to_key
    
    def largest_number(nums):
        strs = sorted(map(str, nums),
                      key=cmp_to_key(lambda x, y: -1 if x + y > y + x else 1))
        return "0" if strs[0] == "0" else "".join(strs)
    java
    import java.util.*;
    
    class Solution {
        static String largestNumber(int[] nums) {
            String[] s = new String[nums.length];
            for (int i = 0; i < nums.length; i++) s[i] = String.valueOf(nums[i]);
            Arrays.sort(s, (x, y) -> (y + x).compareTo(x + y));
            if (s[0].equals("0")) return "0";
            return String.join("", s);
        }
    }
  8. 8

    Sort characters by frequency, highest first.

    medium

    Count characters, then sort the distinct characters by count, descending, and repeat each by its count. Ties may come out in any order unless the question fixes one. A bucket sort by frequency gives O(n). Time O(n + k log k) for k distinct characters, space O(n).. Edge cases: ties, uppercase and lowercase as distinct, empty string.

    python
    from collections import Counter
    
    def frequency_sort(s):
        return "".join(ch * c for ch, c in Counter(s).most_common())
    java
    import java.util.*;
    
    class Solution {
        static String frequencySort(String s) {
            Map<Character, Integer> cnt = new HashMap<>();
            for (char ch : s.toCharArray()) cnt.merge(ch, 1, Integer::sum);
            List<Character> keys = new ArrayList<>(cnt.keySet());
            keys.sort((a, b) -> cnt.get(b) - cnt.get(a));
            StringBuilder sb = new StringBuilder();
            for (char ch : keys)
                for (int i = 0; i < cnt.get(ch); i++) sb.append(ch);
            return sb.toString();
        }
    }
  9. 9

    Kth largest element without sorting the whole array (quickselect).

    hard

    The kth largest sits at index n - k of the sorted array. Partition around a random pivot as in quick sort; if the pivot lands on the target index you are done, otherwise continue only into the side that contains it. The expected work is n + n/2 + n/4 and so on, which is O(n). Time O(n) average, O(n^2) worst; space O(1).. Edge cases: k = 1 (maximum), k = n (minimum), duplicate values.

    python
    import random
    
    def find_kth_largest(a, k):
        target, lo, hi = len(a) - k, 0, len(a) - 1
        while True:
            p = random.randint(lo, hi)
            a[p], a[hi] = a[hi], a[p]
            pivot, i = a[hi], lo
            for j in range(lo, hi):
                if a[j] < pivot:
                    a[i], a[j] = a[j], a[i]
                    i += 1
            a[i], a[hi] = a[hi], a[i]
            if i == target:
                return a[i]
            if i < target:
                lo = i + 1
            else:
                hi = i - 1
    java
    import java.util.*;
    
    class Solution {
        static int findKthLargest(int[] a, int k) {
            Random rnd = new Random();
            int target = a.length - k, lo = 0, hi = a.length - 1;
            while (true) {
                int p = lo + rnd.nextInt(hi - lo + 1);
                int t = a[p]; a[p] = a[hi]; a[hi] = t;
                int pivot = a[hi], i = lo;
                for (int j = lo; j < hi; j++) {
                    if (a[j] < pivot) { t = a[i]; a[i] = a[j]; a[j] = t; i++; }
                }
                t = a[i]; a[i] = a[hi]; a[hi] = t;
                if (i == target) return a[i];
                if (i < target) lo = i + 1;
                else hi = i - 1;
            }
        }
    }
  10. 10

    Count inversions: pairs i < j with a[i] > a[j].

    hard

    Run merge sort and count during the merge. When the right element is placed before remaining left elements, it forms an inversion with each of them, so add the number of left elements still waiting. Counting this way avoids the O(n^2) pair scan. Time O(n log n), space O(n).. Edge cases: sorted input (0), reverse input (n(n-1)/2, use long), equal values (not inversions).

    python
    def count_inversions(a):
        def sort(x):
            if len(x) <= 1:
                return x, 0
            m = len(x) // 2
            left, cl = sort(x[:m])
            right, cr = sort(x[m:])
            inv, i, j, out = cl + cr, 0, 0, []
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    out.append(left[i])
                    i += 1
                else:
                    out.append(right[j])
                    j += 1
                    inv += len(left) - i
            out.extend(left[i:])
            out.extend(right[j:])
            return out, inv
        return sort(a)[1]
    java
    import java.util.*;
    
    class Solution {
        static long countInversions(int[] a, int lo, int hi, int[] t) {
            if (hi - lo < 2) return 0;
            int m = (lo + hi) >>> 1;
            long inv = countInversions(a, lo, m, t) + countInversions(a, m, hi, t);
            int i = lo, j = m, k = lo;
            while (i < m && j < hi) {
                if (a[i] <= a[j]) t[k++] = a[i++];
                else { t[k++] = a[j++]; inv += m - i; }
            }
            while (i < m) t[k++] = a[i++];
            while (j < hi) t[k++] = a[j++];
            for (k = lo; k < hi; k++) a[k] = t[k];
            return inv;
        }
        // call: countInversions(a, 0, a.length, new int[a.length]);
    }
  11. 11

    What does it mean for a sort to be stable, and why does it matter?

    medium

    A stable sort keeps equal keys in their original relative order. This matters when you sort records by more than one key: sort by the secondary key first, then by the primary key with a stable sort, and the secondary order survives within ties. Merge sort, insertion sort and Timsort are stable; typical quick sort and heap sort are not.

Frequently asked questions

Which sorting algorithm should I use in an interview?

Use the library sort unless asked to implement one. If asked, merge sort is the safest to write correctly and quick sort is the most commonly requested.

Why is quick sort used in practice despite O(n^2) worst case?

It sorts in place with good cache behaviour, and a random or median-of-three pivot makes the worst case very unlikely. Introsort adds a heap sort fallback to guarantee O(n log n).

Can any comparison sort beat O(n log n)?

No. A comparison sort needs at least log2(n!) comparisons, which is about n log n. Counting, radix and bucket sort avoid comparisons and can be linear for suitable inputs.

What sort does Python use?

Timsort, which is stable and takes advantage of runs that are already sorted. Python sorted also accepts a key function, which is cleaner than a comparator.

How is sorting related to intervals problems?

Many interval problems start by sorting on the start time. See merge intervals questions.

Related guides

More in DSA Interview Questions

See all in this section