Chapter 14

Home

Refactoring: Using Built-in Sort

Now that you understand how sorting works, never write your own sort in a contest. The built-in sort is faster, correct, and one line.

Before vs After

Replace your 8-line bubble sort with a single function call — O(N log N) instead of O(N²).

C++ — before

void bubble_sort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

C++ — after

sort(arr.begin(), arr.end());  // O(N log N)

#include <algorithm> (already in <bits/stdc++.h>).

Rust — before

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n - 1 {
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

Rust — after

arr.sort();  // O(N log N)

.sort() is a method on Vec<T> and slices.

Custom Sorting

Sometimes you need to sort by a different order — descending, or by a specific field. Both languages let you provide a custom comparator.

C++ — sort descending

sort(arr.begin(), arr.end(), greater<int>());

// or a custom lambda:
sort(arr.begin(), arr.end(),
     [](int a, int b) { return a > b; });

Rust — sort descending

arr.sort_by(|a, b| b.cmp(a));
// or:
arr.sort();
arr.reverse();

Problem: Sort then Solve

Sort the array first, then solve the problem. This pattern appears constantly — finding the median, checking if two arrays are anagrams, scheduling problems.

Problem: Find the median

Given N (odd), sort the array and print the middle element.

Sample input:
5
8 3 9 1 6

Expected output:
6

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    sort(arr.begin(), arr.end());
    cout << arr[n / 2] << "\n";  // middle index
    return 0;
}

Rust

use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().lock().read_to_string(&mut input).unwrap();
    let nums: Vec<i32> = input
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    let n = nums[0] as usize;
    let mut arr: Vec<i32> = nums[1..=n].to_vec();
    arr.sort();
    println!("{}", arr[n / 2]);
}

💡 Sort-first thinking

Many problems become easy once the data is sorted. "Is this a permutation of that?" Sort both — if they're identical, yes. "What's the closest pair?" Sort first, then check adjacent elements.

Key Takeaways

Practice