Why Sorting Matters

The problem

You've got a list of 50,000 customer emails and you need two things from it: a way to check "is this email already in the list?" fast, and a way to strip out the duplicates someone's messy import created. You wire up the obvious version. It works on your test data of ten rows. On the real file, the page spins for eight seconds and your laptop fan spins up.

The frustrating part is that nothing about the task is hard. Checking membership and removing duplicates are easy ideas. They only feel slow because the data is a shapeless jumble. Give it some structure first and both problems nearly solve themselves. That structure is sorted order, and it's the quiet prerequisite behind a huge fraction of the algorithms you'll ever write.

A first attempt

On unsorted data, every question means scanning. To dedup, you compare each element against every element you've already kept:

def dedup_naive(nums):
    result = []
    for x in nums:
        if x not in result:   # this membership check is itself a full scan
            result.append(x)
    return result

Every x not in result walks the whole result list. That's a loop inside a loop: O(n²). For 50,000 items that's 2.5 billion comparisons. And searching the raw list for one email is O(n) every single time — do it for every incoming email and you're back to O(n²) again. The data's lack of order is taxing you on every single operation.

The insight

Pay the ordering cost once, up front, and every later operation gets cheap. Sorting takes O(n log n) — more than a single scan, but you do it a single time. After that:

• Duplicates sit next to each other, so one pass removes them.
• Membership becomes binary search — O(log n) per lookup instead of O(n).
• The min and max are just the first and last elements.
• "Are any two values close?" only needs to compare neighbours.

Sorting isn't the answer to a problem. It's the setup that makes a dozen other problems trivial. That's why it earns its own module.

How it works

Here's the pattern almost every sorting-based solution follows.

Watch how the shapeless list turns into something you can just walk:

raw:     [ 5  1  5  3  1  2  3 ]      duplicates scattered, no structure
sorted:  [ 1  1  2  3  3  5  5 ]      dupes now adjacent →  keep first of each run
unique:  [ 1  2  3  5 ]              one clean pass, O(n)

The code

Sort first, then a single pass removes duplicates. Every language ships a fast O(n log n) sort, so lean on it.

def unique_sorted(nums):
    nums.sort()                      # O(n log n)
    result = []
    for x in nums:                   # O(n) single pass
        if not result or result[-1] != x:
            result.append(x)
    return result

function uniqueSorted(nums: number[]): number[] {
  nums.sort((a, b) => a - b); // numeric sort, O(n log n)
  const result: number[] = [];
  for (const x of nums) {
    if (result.length === 0 || result[result.length - 1] !== x) {
      result.push(x);
    }
  }
  return result;
}

import java.util.Arrays;

int[] uniqueSorted(int[] nums) {
    Arrays.sort(nums);               // O(n log n)
    int k = 0;
    for (int x : nums) {             // O(n) single pass
        if (k == 0 || nums[k - 1] != x) nums[k++] = x;
    }
    return Arrays.copyOf(nums, k);
}

#include <stdlib.h>

int cmp(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);        // safe, no overflow
}

// sorts in place, compacts unique values to the front, returns new length
int unique_sorted(int *nums, int n) {
    qsort(nums, n, sizeof(int), cmp);   // O(n log n)
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (k == 0 || nums[k - 1] != nums[i]) nums[k++] = nums[i];
    }
    return k;
}

#include <vector>
#include <algorithm>
using namespace std;

vector<int> uniqueSorted(vector<int> nums) {
    sort(nums.begin(), nums.end());     // O(n log n)
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    return nums;
}

Complexity

Compare that to the naive O(n²) dedup: at 50,000 items you go from ~2.5 billion operations down to under a million. Same idea, sorted first.

When to use it

Practice

Recap

• Sorting is a one-time O(n log n) investment that makes dedup, search, min/max, and grouping cheap or trivial.
• After sorting, related values are adjacent — so most problems reduce to a single pass or a binary search.
• Sort when you'll reuse the ordered data; skip it for one-off lookups where a scan wins.