Skip to content
Tutorials Center
My learning

Topics

Lesson 87 of 225 ยท Sorting

Sorting Problems and Applications

Solve classic sorting problems in Python: merge intervals, meeting rooms, k-th largest, a custom comparator, sort by frequency and external sorting.

Knowing how sorting algorithms work is one skill. Knowing when sorting is the key to a problem is another, and it is the one that wins interviews and real projects. A surprising number of problems become easy once the data is in order: duplicates sit next to each other, overlapping intervals touch, the smallest and largest values are at the ends, and two pointers can sweep through in one pass.

In this lesson you will solve the classics: merge overlapping intervals, check and count meeting rooms, find the k-th largest element in three ways, build the largest number with a custom comparator, sort by frequency, and see how data too large for memory is sorted. For each problem we start with a brute-force idea, then show the better solution and its complexity. We use Python's built-in sorted as the sorting step, which costs O(n log n); see Shell Sort, Timsort and Hybrid Sorts for what happens inside.

The "sort first" mindset

Ask yourself these questions when you read a problem:

  • Does the answer depend on neighbors in some order (closest pair, adjacent duplicates, overlapping ranges)? Sort, then scan neighbors.
  • Is the order of processing free to choose? Sort by a good key (start time, end time, deadline, size) and process greedily; see Greedy Algorithms.
  • Do you need the smallest/largest k items? Maybe a heap or quickselect beats a full sort.
  • Is the comparison unusual (concatenate to get the biggest number)? Write a custom comparator.

The price of sorting is O(n log n). If the rest of the algorithm is O(n), the total is O(n log n), and this usually beats an O(nยฒ) brute force by a wide margin.

Problem 1: merge overlapping intervals

Given a list of intervals such as [1, 3], [2, 6], [8, 10], [9, 12], merge all that overlap. Intervals that merely touch ([1, 4] and [4, 5]) also merge here.

Brute force. Repeatedly look at all pairs, merge any that overlap, and start again until no pair overlaps. That can take O(nยฒ) per round and several rounds.

Sort by start. Once intervals are sorted by start time, an interval can only overlap with the last merged interval. Compare its start with the last merged end: if it is within reach, extend the end; otherwise start a new group.

TEXT
sorted:   [1,3] [2,6] [8,10] [9,12]

[1,3]
[2,6]  starts at 2 <= end 3  -> merge  -> [1,6]
[8,10] starts at 8 >  end 6  -> new    -> [1,6] [8,10]
[9,12] starts at 9 <= end 10 -> merge  -> [1,6] [8,12]
Python Merge intervals: brute force and sorted

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sorted solution is O(n log n) for the sort plus O(n) for the scan, and O(n) extra space for the output. Notice max(...) on the end: when one interval sits entirely inside another, the end must not shrink. Forgetting that max is the classic bug. The same sorting trick underlies Interval Scheduling and Meeting Rooms.

Problem 2: meeting rooms

Part A. Can one person attend all meetings, given (start, end) pairs? Sort by start; the answer is no if any meeting starts before the previous one ends.

Part B. What is the minimum number of rooms needed? Think of a sweep: walk through time, +1 room when a meeting starts and -1 when one ends. The maximum overlap is the answer. A neat way: sort the start times and the end times separately and walk through them with two pointers.

Python Meeting rooms: attend all and minimum rooms

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both room counters cost O(n log n) for sorting and use O(n) space. The two-pointer version avoids a heap. The heap version has the advantage that it can tell you which room is free next. A meeting that ends at 10 does not conflict with one starting at 10: the comparisons use <= and >= for that reason.

Problem 3: the k-th largest element

Given an unsorted list, find the k-th largest value (k = 1 is the maximum). There are three standard ways, each with a different trade-off:

Approach Time Extra space Comment
Sort, then index O(n log n) O(n) simplest; sorted(a)[-k]
Min-heap of size k O(n log k) O(k) good for streams; see Top-K and Streaming Problems
Quickselect O(n) expected, O(nยฒ) worst O(1) or O(n) see Quick Sort
Python Three ways to find the k-th largest

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the duplicate 10 in the data: the 2nd and 3rd largest are both 10, because the problem counts positions in sorted order, not distinct values. Read problem statements for this detail. Python also offers heapq.nlargest(k, a)[-1]; see Heaps in Python: heapq.

Problem 4: the largest number (custom comparator)

Given non-negative integers such as [3, 30, 34, 5, 9], arrange them so that, concatenated, they form the largest possible number. Sorting numerically fails: 9 > 5 > 34 > 30 > 3 gives 9534303, but 9534330 is bigger. The right rule compares pairs of strings: put a before b if a + b > b + a.

TEXT
3 vs 30:  "330" vs "303" -> 330 is bigger, so 3 goes before 30
34 vs 3:  "343" vs "334" -> 343 is bigger, so 34 goes before 3

Python's sorted takes a key, not a comparator. Use functools.cmp_to_key to turn a two-argument comparison (returning negative, zero or positive) into a key.

Python Largest number with cmp_to_key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The comparison is consistent (transitive), which is required for a sort to work. Always check this property when you invent a comparator: an inconsistent one produces unpredictable results. Complexity: O(n log n) comparisons, each comparing strings of length up to the number of digits.

Problem 5: sort by frequency

Sort characters or numbers by how often they occur, most frequent first, with ties broken by smallest value. This is a perfect case for a multi-key sort: count with Counter, then use a tuple as the key. A tuple key compares its first element, then the second, and so on. Negating the count flips the order for that part only.

Python Sort by frequency with a tuple key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cost is O(n) to count plus O(n log n) to sort. If the counts are small integers, counting sort on the frequencies, or a bucket per frequency, can make this O(n); see Hashing Patterns for the bucket approach.

Problem 6: closest pair of values

Find the smallest absolute difference between any two numbers in a list. Brute force compares every pair: O(nยฒ). After sorting, the closest pair must be adjacent, because if two values have another value between them, the gap to that middle value is smaller. That gives O(n log n).

Python Smallest difference between two numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorting-then-neighbors also solves duplicate detection (Hashing Patterns does it with a set in O(n) time, trading memory), pairs with a target sum with two pointers, and anagram grouping (sort the letters to form a key).

External sorting: when data does not fit in memory

What if you must sort 100 GB on a machine with 8 GB of memory? You cannot call sorted. External merge sort has two phases:

  1. Create runs. Read a chunk that fits in memory, sort it, and write it back out as a sorted file (a run). Repeat until all data is in runs.
  2. Merge runs. Open all runs at once and merge them with a min-heap holding one element from each run, writing the smallest to the output each time. This is the k-way merge from Merging K Sorted Lists.

Disk reads are slow, so the goal is to read and write sequentially in big blocks and to minimize passes over the data. Databases use the same idea for ORDER BY on big tables. We can simulate it with lists as stand-ins for files, and heapq.merge, which merges sorted iterables lazily.

Python External merge sort simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With r runs the heap holds only r elements, so memory stays small. The time is O(n log r) for the merge. If there are too many runs to open at once, merge them in several passes. The total number of passes is about log base (fan-in) of the number of runs.

Common mistakes

  • Sorting when a simpler tool is enough. Finding only the maximum needs max, O(n), not a sort.
  • Mutating the input by accident. list.sort() sorts in place and returns None; sorted() returns a new list. Use the one you mean.
  • Shrinking the interval end. Always take max(old_end, new_end) when merging.
  • Wrong comparator. If compare(a, b) and compare(b, a) are not opposites, or the order is not transitive, the result is undefined.
  • Treating "k-th largest" as "k-th distinct largest". Check whether duplicates count.
  • Using < where <= is needed at interval boundaries. Decide whether touching intervals overlap and test it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. After sorting intervals by start time, when should the current interval be merged into the last merged one?

    If the next interval starts no later than the group's current end, they overlap (or touch), so the group's end becomes the maximum of both ends.
  2. 2. What is the time complexity of the sort-and-scan solution for merging n intervals?

    Sorting costs O(n log n) and the single scan afterwards is O(n), so sorting dominates.
  3. 3. Why does comparing the strings a + b and b + a give the largest concatenated number?

    The pair rule is transitive, so sorting with it places every number where the combined string is maximal. Plain numeric order fails for cases like 3 and 30.
  4. 4. Which approach uses O(k) extra space to find the k-th largest element in a stream?

    The heap holds the k largest values; its smallest element is the k-th largest. Each new value costs O(log k).
  5. 5. In external merge sort, what does the min-heap hold during the merge phase?

    The heap always contains the front element of each run, so its size is the number of runs, and popping gives the next smallest value overall.

Summary

  • Sorting often turns a hard problem into a scan: neighbors become meaningful, and a greedy order becomes possible.
  • Merge intervals by sorting on start time and extending the last group with max of the ends: O(n log n).
  • Minimum meeting rooms is the maximum overlap, found with sorted starts and ends or with a heap of end times.
  • The k-th largest can be found by sorting, with a size-k heap, or with quickselect; pick by time and memory needs.
  • A custom comparator via cmp_to_key solves orderings such as the largest concatenated number; the comparator must be consistent.
  • Tuple keys give multi-key sorts such as frequency descending then value ascending.
  • External sorting creates sorted runs that fit in memory and merges them with a heap.

Next: Trees, the first non-linear data structure in this tutorial.