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
10

DSA · Lesson 10 of 20 · 4 min

Sorting Algorithms I: Basics

You're asked about these O(N^2) algorithms to prove you understand fundamentals, not because you'll use them on large datasets.

After this, you'll be able to explain the trade-offs between Bubble, Selection, and Insertion sort. You'll know which one is sometimes used in production and why. This is a common first-pass filter in interviews to see if you can analyze algorithms at all.

Why you can't just say "I'd use .sort()"

In an interview, saying you'd use the native Array.prototype.sort() is the right answer for a production problem, but it dodges the question. The interviewer wants to see if you can reason about algorithms from first principles.

They are testing your vocabulary and understanding of three key concepts:

  1. Time Complexity: How does performance scale with input size? (e.g., O(N²))
  2. Space Complexity: How much extra memory is needed? An in-place sort uses O(1) extra space.
  3. Stability: Does the algorithm preserve the original relative order of equal elements? This is crucial for multi-level sorting in UIs.

Your goal is to show you can analyze a simple algorithm on these three axes. The O(N²) sorts are just the vehicle for that discussion.

The three quadratic sorts: a comparison

All three of these sorts have a worst-case time complexity of O(N²) because they use nested loops to iterate through the array. Their core logic, however, is different.

Bubble Sort is the simplest. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest unsorted element "bubbles" to its correct position in each pass. It's famous for being easy to write and easy to get wrong.

Selection Sort is about minimizing swaps. In each pass, it finds the smallest remaining element in the unsorted portion and swaps it into its correct position. It makes exactly N-1 swaps, which can be useful if writes are expensive.

Insertion Sort builds the final sorted array one item at a time. It takes each element from the input and inserts it into its correct position within the already-sorted part of the array.

This diagram shows the fundamental difference in their inner loops.

The trap: Stating the complexity isn't enough. You must explain why it's O(N²) by describing the nested loops. For Bubble Sort, you'd say, "The outer loop runs N times, and the inner loop runs, on average, N/2 times, giving us a time complexity of O(N²)."

When a "bad" sort is the right choice

Of these three, Insertion Sort is the only one with practical applications. While its worst-case is O(N²), its best-case is O(N). This happens when the array is already sorted or nearly sorted.

Because it performs well on small or mostly-ordered collections, it's often used as a final step in more complex algorithms. Timsort, the algorithm used in V8's Array.prototype.sort, uses Insertion Sort for small partitions of the array (e.g., < 64 elements). Mentioning this shows you've connected the theory to real-world systems.

The trap: A candidate is asked to sort a list of 10 million log entries that are streamed in chronological order, with only a few arriving out of order. A naive answer is "Quicksort". A better answer is to recognize the data is "nearly sorted" and suggest that Insertion Sort could be unusually effective here.

Here is a clean implementation of Insertion Sort. You should be able to write this from memory.

function insertionSort<T>(arr: T[]): T[] {
  const n = arr.length;

  for (let i = 1; i < n; i++) {
    // The element we want to position correctly
    const current = arr[i];
    
    // The last index of the sorted portion
    let j = i - 1;

    // Shift elements in the sorted portion to the right
    // until we find the correct spot for `current`.
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // Insert `current` into its correct position
    arr[j + 1] = current;
  }
  return arr;
}

How to talk about stability and space

Stability is a common follow-up question. A stable sort preserves the original order of equal elements.

Imagine a user table sorted by signupDate. If you then sort by lastName, you want all the "Smiths" to still be ordered by their original signupDate. An unstable sort might shuffle them randomly.

  • Stable: Bubble Sort, Insertion Sort. They only swap adjacent elements or shift elements one at a time, which preserves relative order.
  • Unstable: Selection Sort. It can take an element from the end of the array and swap it with one at the beginning, jumping over other elements (including equal ones) and changing their relative order.

All three are in-place sorts, meaning they use O(1) auxiliary space. They sort the array by modifying it directly without creating a new copy. This is a key advantage when memory is constrained.

Try it

Implement Selection Sort from memory in 10 minutes. Then, create a small array of objects, like [{ value: 5, id: 'a' }, { value: 3, id: 'b' }, { value: 5, id: 'c' }]. Manually trace your sort on this array to prove to yourself why it is not stable.

Next: We'll cover the O(N log N) algorithms that you actually use for large datasets in "Sorting Algorithms II: Divide & Conquer".

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice this pattern
Previous

Tree Traversal Algorithms (BFS & DFS)

Next

Sorting Algorithms II: Divide & Conquer