Frontend School
DashboardProblemsLearnPracticeMock InterviewReportsStatsBuy Credits
DashboardProblemsLearnPracticeMock Interview
DSA for Frontend Engineers
  1. 1.Introduction to DSA for Frontend Engineers
  2. 2.JavaScript Fundamentals for DSA
  3. 3.Arrays and Strings: Core Techniques
  4. 4.Objects and Hash Maps in JavaScript
  5. 5.Linked Lists: Building Blocks
  6. 6.Stacks and Queues: LIFO & FIFO
  7. 7.Recursion and Iteration: Problem Solving Paradigms
  8. 8.Introduction to Trees: Binary Trees & BSTs
  9. 9.Tree Traversal Algorithms (BFS & DFS)
  10. 10.Sorting Algorithms I: Basics
  11. 11.Sorting Algorithms II: Divide & Conquer
  12. 12.Searching Algorithms: Linear & Binary Search
  13. 13.Graphs: Representation & Traversals
  14. 14.Dynamic Programming I: Memoization
  15. 15.Heaps and Priority Queues
  16. 16.Tries (Prefix Trees) for Autocomplete & Search
  17. 17.Advanced Graph Algorithms: Shortest Paths & MST
  18. 18.Dynamic Programming II: Tabulation & Frontend Patterns
  19. 19.Frontend System Design with DSA Lens
  20. 20.Interview Strategies & Advanced Problem Solving
DSA for Frontend Engineers
11

DSA · Lesson 11 of 20 · 4 min

Sorting Algorithms II: Divide & Conquer

This is how you explain the trade-offs between the two most common O(n log n) sorting algorithms in an interview.

After the O(n²) sorts, we get to the ones you'll actually be asked to implement and analyze: Merge Sort and Quick Sort. They both use a "divide and conquer" strategy, but their performance characteristics are opposites. Knowing which to use, and why, is the entire point.

Merge Sort: Stable and predictable

Merge Sort divides an array in half, recursively sorts each half, and then merges the two sorted halves back together. Its performance is consistent, which is its main selling point.

The work happens in the merge step. You have two sorted arrays, and you create a new one by walking through both, picking the smaller element at each step, until you've exhausted both inputs.

The trade-offs

Merge Sort's time complexity is O(n log n) in all cases—best, average, and worst. This predictability is valuable. If you're sorting data for a UI render that has to happen in under 16ms, you can't afford a surprise O(n²) hiccup.

It's also a stable sort. If two elements are considered equal, their original relative order is preserved. This is critical if you're sorting a list of objects by one property, then another. For example, sorting users by last name, where users with the same last name should remain in their original order.

The major downside is space. A standard implementation requires O(n) auxiliary space to hold the merged arrays. This can be a deal-breaker for very large datasets in memory-constrained environments.

The code

This implementation shows the classic out-of-place merge. Note how the merge function does the heavy lifting.

function mergeSort<T>(arr: T[]): T[] {
    if (arr.length <= 1) {
        return arr;
    }

    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}

function merge<T>(left: T[], right: T[]): T[] {
    const result: T[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // Append remaining elements from either left or right
    return result
        .concat(left.slice(leftIndex))
        .concat(right.slice(rightIndex));
}

Quick Sort: Fast, but with a weak spot

Quick Sort also divides the work, but differently. It picks an element (the "pivot"), and partitions the array so that all elements smaller than the pivot come before it, and all elements larger come after. The pivot is now in its final sorted position. Then it recursively sorts the sub-arrays to the left and right of the pivot.

Unlike Merge Sort, there's no separate "combine" step. The work is done up-front in the partitioning.

The trade-offs

Quick Sort's average time complexity is O(n log n) and it's often faster in practice than Merge Sort. This is because it has better cache locality and the partitioning can be done in-place, without allocating new arrays.

Its space complexity is O(log n) on average, for the recursion call stack. This is a huge advantage over Merge Sort's O(n).

The trap: The pivot is everything. If you consistently pick a bad pivot (like the smallest or largest element), the partitions become extremely unbalanced. In the worst case, you're just splitting off one element at a time, which degrades the time complexity to O(n²). A sorted array is a classic trigger for this worst-case behavior if you always pick the last element as the pivot.

Quick Sort is also not stable. The partitioning process shuffles equal elements around, so their original order is not guaranteed.

The code

This implementation sorts in-place, modifying the input array directly. The partition function rearranges a sub-array and returns the final index of the pivot.

function quickSort<T>(arr: T[], low: number = 0, high: number = arr.length - 1): void {
    if (low < high) {
        const pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

function partition<T>(arr: T[], low: number, high: number): number {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
        }
    }

    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Place pivot
    return i + 1;
}

How to answer "Merge Sort vs. Quick Sort"

This is a classic question. Don't just list complexities. Show you understand the practical implications.

Your answer should cover these points:

  • Memory: Is the dataset huge? Quick Sort's O(log n) space is a clear winner over Merge Sort's O(n) if memory is a concern.
  • Stability: Do you need to preserve the order of equal elements? Use Merge Sort. Quick Sort is not stable.
  • Predictability: Do you need a performance guarantee? Merge Sort's worst case is the same as its average case, O(n log n). Quick Sort's O(n²) worst case, while rare with good pivot selection, can be a risk.
  • Context: For a frontend developer, it's impressive to know that browser engines often use hybrid algorithms. V8's Array.prototype.sort uses Timsort (a hybrid of Merge Sort and Insertion Sort) for performance, stability, and memory efficiency.

The trap: A candidate says "Quick Sort is faster." A senior engineer says "Quick Sort is often faster in practice for generic data due to its in-place nature and cache efficiency, but its O(n²) worst-case makes it unsuitable for applications requiring guaranteed performance, where Merge Sort would be a safer choice."

Try it

Implement quickSort, but modify the partition function to use a random element as the pivot instead of the last one. This is a simple way to make the worst-case O(n²) performance extremely unlikely in practice.

Next: We'll see how sorted data enables much faster lookups in Searching Algorithms: Linear & Binary Search.

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice this pattern
Previous

Sorting Algorithms I: Basics

Next

Searching Algorithms: Linear & Binary Search