In a real-world Ruby project, you're almost never going to write your own sorting algorithm. You'll call .sort or .sort_by and let the C-implementation of Timsort handle the heavy lifting. But if you've ever sat through a technical interview or tried to optimize a very specific data stream, you'll realize that understanding how data moves during a sort is a superpower.

Let's get our hands dirty. I've got this array of unsorted sensor readings—just some integers representing temperatures—and I want to sort them from lowest to highest without using the built-in methods.

readings = [64, 34, 25, 12, 22, 11, 90]

Getting the biggest fish to the end

My first instinct when I'm explaining this is usually the Bubble Sort. It's not efficient, but it's visual. The idea is to compare two side-by-side elements and swap them if they're in the wrong order. Let's try a single pass through the array and see what happens.

def bubble_pass(arr)
  (0...arr.length - 1).each do |i|
    if arr[i] > arr[i + 1]
      arr[i], arr[i + 1] = arr[i + 1], arr[i]
    end
  end
  arr
end

readings = [64, 34, 25, 12, 22, 11, 90]
p bubble_pass(readings) 
# Output: [34, 25, 12, 22, 11, 64, 90]

Wait, that didn't fully sort the list. But look at the end: 90 and 64 are now in their correct final positions. The largest value "bubbled up" to the top. To actually sort the whole thing, I need to repeat this process. I can't just run it once; I have to run it enough times that every single element has a chance to move to its correct spot.

def bubble_sort(arr)
  n = arr.length
  # We need to repeat the pass n times to guarantee everything is sorted
  n.times do
    (0...n - 1).each do |i|
      if arr[i] > arr[i + 1]
        arr[i], arr[i + 1] = arr[i + 1], arr[i]
      end
    end
  end
  arr
end

p bubble_sort([64, 34, 25, 12, 22, 11, 90])
# Output: [11, 12, 22, 25, 34, 64, 90]

Cleaning up the redundancy

Now, if I'm being honest, the version above is sloppy. If the array becomes sorted halfway through the loop, the code keeps grinding away until the n.times block finishes. That's a waste of CPU cycles. I can fix this by introducing a "swapped" flag. If I go through a whole pass without swapping anything, I know the array is sorted and I can bail early.

def optimized_bubble_sort(arr)
  n = arr.length
  loop do
    swapped = false
    (0...n - 1).each do |i|
      if arr[i] > arr[i + 1]
        arr[i], arr[i + 1] = arr[i + 1], arr[i]
        swapped = true
      end
    end
    break unless swapped
  end
  arr
end

This is better, but Bubble Sort is still O(n²). If I gave this a list of 100,000 temperatures, my laptop fan would start screaming. I need something that doesn't just nudge elements one by one.

Splitting the problem in half

This is where Quick Sort comes in. Instead of swapping neighbors, I'm going to pick a "pivot" element and split the rest of the array into two piles: things smaller than the pivot and things larger than the pivot. Then, I'll do the same thing to those piles. This is recursion in its purest form.

Let's try to implement this using Ruby's select method to keep the logic clean:

def quick_sort(arr)
  # Base case: an array of 0 or 1 elements is already sorted
  return arr if arr.length <= 1

  # Pick the middle element as the pivot
  pivot = arr.delete_at(arr.length / 2)
  
  # Split the remaining elements into two groups
  left = arr.select { |x| x <= pivot }
  right = arr.select { |x| x > pivot }

  # Recursively sort the left and right, then sandwich the pivot in between
  return quick_sort(left) + [pivot] + quick_sort(right)
end

p quick_sort([64, 34, 25, 12, 22, 11, 90])
# Output: [11, 12, 22, 25, 34, 64, 90]

I love this implementation because it reads like a sentence: "Sort the small stuff, put the pivot in the middle, then sort the big stuff." It's significantly faster (O(n log n) on average) because it aggressively reduces the size of the problem with every step.

Why we usually just call .sort

So, why don't we write quick_sort every time? Because the version I just wrote creates a lot of intermediate arrays in memory (via select), which puts pressure on the Ruby Garbage Collector. The built-in .sort is written in C and manages memory far more efficiently.

The takeaway here isn't to replace the standard library; it's to recognize the pattern. Bubble sort is a "linear" mindset—checking things one by one. Quick sort is a "divide and conquer" mindset—breaking a big problem into smaller, identical problems. Once you see that, you'll start seeing it everywhere in software engineering.

📋 Practical Task

Implementing a Stable Quick Sort for User Profiles

In the previous lesson, our quick_sort worked for integers, but in the real world, we often sort objects. Imagine you have a list of User profiles, and you want to sort them by their age. However, you want to ensure that if two users have the same age, their original relative order is preserved (this is called a "stable sort").

Your Task:

• Create a User struct or class with name and age attributes.
• Create an array of at least 5 User objects, including at least two users with the same age.
• Modify the quick_sort logic from the lesson to accept a block or a lambda so it can sort based on a specific attribute (like age) rather than the object itself.
• Verify that the users are sorted by age and that the users with the same age remain in the order they were originally placed in the array.