Sorting Algorithms Questions

Assesses knowledge of common sorting algorithms and the ability to implement them. Topics include understanding and implementing quicksort, mergesort, heapsort, insertion sort and other common sorts, analyzing time and space complexity in average and worst cases, algorithm stability, in place versus out of place behavior, recursion versus iterative implementations, practical trade offs for different input sizes and distributions, optimization for small arrays, and writing correct, tested code from scratch. Candidates should be able to justify algorithm choice for a given scenario and reason about performance constraints.

EasyTechnical

21 practiced

Write a function that checks whether an array is sorted in non-decreasing order and returns the first index where the order is violated, or -1 if sorted. Implement in the language of your choice and analyze complexity. Example: [1,2,2,3] -> -1, [1,3,2] -> 1.

Sample Answer

Approach: scan the array once and compare each element to its predecessor; return the index of the first element that is smaller than the previous (violation of non-decreasing order). This is O(n) time and O(1) extra space.

python

def first_unsorted_index(arr):
    """
    Return the first index i where arr[i] < arr[i-1], meaning order is violated.
    If array is non-decreasing, return -1.
    """
    if not arr:           # optional: empty array is considered sorted
        return -1

    for i in range(1, len(arr)):
        if arr[i] < arr[i - 1]:
            return i
    return -1

# Examples
# [1,2,2,3] -> -1
# [1,3,2]   -> 2 (index of 2). If you expect 1 (the earlier element), return i-1 instead.

Key points:- This returns the index of the element that breaks the order (i). If the requirement is to return the index of the prior element (the one causing the issue), return i-1.- Time complexity: O(n) — single pass.- Space complexity: O(1).Edge cases:- Empty array -> -1.- Single-element array -> -1.- Arrays with duplicates handled correctly.

MediumTechnical

24 practiced

Pivot choice influences quicksort performance. Implement median-of-three pivot selection and integrate it into a quicksort implementation. Explain why median-of-three helps and situations where it may not improve performance.

Sample Answer

To reduce worst-case pivot choices, use median-of-three: pick median of first, middle, last elements as pivot. This reduces chance of highly unbalanced partitions on partially sorted inputs and gives better average performance.

cpp

#include <algorithm>
#include <vector>
#include <utility>

// In-place quicksort with median-of-three pivot selection
void quicksort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;

    // For small partitions, use insertion sort cutoff for better constant factors
    if (hi - lo <= 16) {
        for (int i = lo + 1; i <= hi; ++i) {
            int key = a[i], j = i - 1;
            while (j >= lo && a[j] > key) { a[j+1] = a[j]; --j; }
            a[j+1] = key;
        }
        return;
    }

    int mid = lo + (hi - lo) / 2;
    // median-of-three: arrange lo, mid, hi so that a[mid] is median
    if (a[lo] > a[mid]) std::swap(a[lo], a[mid]);
    if (a[lo] > a[hi]) std::swap(a[lo], a[hi]);
    if (a[mid] > a[hi]) std::swap(a[mid], a[hi]);
    // now a[mid] is median; move it to hi-1 and use as pivot
    std::swap(a[mid], a[hi-1]);
    int pivot = a[hi-1];

    // Partition with two pointers
    int i = lo, j = hi - 1;
    while (true) {
        while (a[++i] < pivot) {}
        while (a[--j] > pivot) {}
        if (i >= j) break;
        std::swap(a[i], a[j]);
    }
    std::swap(a[i], a[hi-1]); // place pivot

    quicksort(a, lo, i - 1);
    quicksort(a, i + 1, hi);
}

void quicksort(std::vector<int>& a) {
    if (!a.empty()) quicksort(a, 0, (int)a.size() - 1);
}

Key points:- Median-of-three reduces probability of picking extreme pivots on sorted or nearly sorted input by using a sample of three.- We place median at hi-1 to simplify partition boundaries and use insertion sort for small arrays (common optimization).Time/space:- Average time: O(n log n), worst-case still O(n^2) (though much less likely).- Space: O(log n) stack on average (recursion), O(n) worst-case.Edge cases / when it may not help:- Random data: small benefit vs simple pivot but still safe.- Adversarial inputs: if adversary knows algorithm and crafts array exploiting median-of-three pattern, worst-case O(n^2) remains.- Extremely small arrays: overhead of median computation may outweigh benefits, hence insertion cutoff.- Duplicate-heavy arrays: median-of-three doesn't address equal-key partitioning; use 3-way partitioning for many duplicates.

MediumTechnical

23 practiced

You need to sort records by multiple keys, for example country, then state, then city, and preserve stability. Describe two approaches: using a composite comparator or stable multi-pass sorts. Provide code sketches and discuss pros and cons.

Sample Answer

Approach summary:1) Composite comparator: build one comparator that compares keys in priority order (country → state → city). Works with a single stable sort if underlying sort is stable (e.g., Java's Collections.sort on Lists uses TimSort which is stable). Simpler and efficient.2) Stable multi-pass sorts: perform stable sorts from least-significant key to most-significant key (city, then state, then country). Each pass is stable so earlier order is preserved.

Composite comparator (Java):

java

Comparator<Record> cmp = Comparator
    .comparing(Record::getCountry)
    .thenComparing(Record::getState)
    .thenComparing(Record::getCity);

// single sort
Collections.sort(records, cmp); // uses stable TimSort in modern JDK

Multi-pass stable sorts (Java):

java

// sort by least significant to most significant
Collections.sort(records, Comparator.comparing(Record::getCity));
Collections.sort(records, Comparator.comparing(Record::getState));
Collections.sort(records, Comparator.comparing(Record::getCountry));

Pros / Cons:- Composite comparator - Pros: One pass (O(n log n)), simpler to reason about, easier to maintain single locale-aware comparator. - Cons: Comparator complexity increases; expensive if comparator invokes heavy logic repeatedly (can mitigate by caching keys).- Multi-pass stable sorts - Pros: Simple per-key comparator, useful when you only have unstable sort implementation but guarantee stable per-pass; good for radix-like scenarios or external sorts. - Cons: Multiple passes cost O(k * n log n) with k keys (or O(k * n) if using linear stable sorts like counting/radix for small domains). More data movement; harder when keys are many or expensive to extract.

Notes:- Ensure null handling and locale/case sensitivity in comparators.- For very large datasets or small-key domains consider radix/counting sort for linear time stability.

MediumTechnical

27 practiced

Implement the merge step used in mergesort: given two adjacent sorted subarrays within a single array A[lo..mid] and A[mid+1..hi], produce a sorted result using O(n) extra space. Provide code in any language and analyze correctness and complexity.

Sample Answer

To merge two adjacent sorted subarrays A[lo..mid] and A[mid+1..hi], copy them into an auxiliary array and perform a two-pointer stable merge back into A.

python

def merge(A, lo, mid, hi):
    """
    Merge sorted subarrays A[lo:mid+1] and A[mid+1:hi+1] into A[lo:hi+1].
    Uses O(n) auxiliary space where n = hi-lo+1. Stable.
    """
    # Copy the relevant slice
    aux = A[lo:hi+1]
    left_start = 0
    left_end = mid - lo       # inclusive index in aux for left part
    right_start = left_end + 1
    right_end = hi - lo       # inclusive index in aux for right part

    i = left_start   # pointer into left half of aux
    j = right_start  # pointer into right half of aux
    k = lo           # write pointer into A

    while i <= left_end and j <= right_end:
        # stable: when equal, take from left (i) first
        if aux[i] <= aux[j]:
            A[k] = aux[i]
            i += 1
        else:
            A[k] = aux[j]
            j += 1
        k += 1

    # copy any remaining elements
    while i <= left_end:
        A[k] = aux[i]; i += 1; k += 1
    while j <= right_end:
        A[k] = aux[j]; j += 1; k += 1

Correctness:- Invariant: at each step, A[lo..k-1] contains the smallest (k-lo) elements from the union of the two halves in sorted order.- Since aux preserves original relative order and we prefer left on ties, the merge is stable.

Complexity:- Time: O(n) where n = hi - lo + 1 (each element examined and moved once).- Space: O(n) auxiliary for the copy. In-place stable merges exist but are more complex and often cost more time.

Edge cases:- One subarray empty (mid < lo or mid >= hi) — loop copies remaining elements correctly.- Duplicate elements — stability preserved.- Large arrays — ensure auxiliary allocation fits memory; consider iterative/blocked merges for very large data.

MediumTechnical

31 practiced

Implement heapsort in Java. Use an array-based max-heap to sort in place with O(1) auxiliary memory (not counting recursion/stack). Explain how building the heap can be done in O(n) time and demonstrate with a sample input.

Sample Answer

To implement heapsort in-place using an array-based max-heap, we:1) Build the max-heap in O(n) by calling heapify (siftDown) from the last parent down to index 0.2) Repeatedly swap the root (max) with the last element, reduce heap size, and siftDown the new root. This sorts ascending in-place with O(1) auxiliary memory.

java

public class HeapSort {
    // Heapsort entry
    public static void heapSort(int[] a) {
        if (a == null || a.length < 2) return;
        int n = a.length;
        // Build max-heap in O(n)
        for (int i = parent(n - 1); i >= 0; i--) siftDown(a, i, n);
        // Extract max and restore heap
        for (int end = n - 1; end > 0; end--) {
            swap(a, 0, end);        // move max to its final position
            siftDown(a, 0, end);    // sift down in reduced heap
        }
    }

    private static int parent(int i) { return (i - 1) / 2; }

    // Sift down element at i within heap size 'n'
    private static void siftDown(int[] a, int i, int n) {
        while (true) {
            int left = 2 * i + 1;
            if (left >= n) break;
            int right = left + 1;
            int largest = (right < n && a[right] > a[left]) ? right : left;
            if (a[largest] <= a[i]) break;
            swap(a, i, largest);
            i = largest;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    // Demo
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 1, 9, 2};
        heapSort(arr);
        // arr -> [1,2,3,4,5,8,9]
        for (int x : arr) System.out.print(x + " ");
    }
}

Why build-heap is O(n): siftDown cost depends on node depth. There are roughly n/2^h nodes at height h, each costing O(h). Summing h * (n/2^h) over h yields O(n) (geometric series), so bottom-up heapify is linear. Overall time: O(n log n) (O(n) build + O(n log n) extraction). Space: O(1) auxiliary. Edge cases: null/empty array, duplicates — all handled.

Unlock Full Question Bank

Get access to hundreds of Sorting Algorithms interview questions and detailed answers.

Join thousands of developers preparing for their dream job.