Sorting Basics

Sorting Basics | Algoryva

First, the naive way

Finding duplicates without ordering

Task: does a list contain any repeated value? With no order, the only general approach is to compare every item with every other item.

For 100,000 items that is about 5 billion comparisons. The comparisons are mostly pointless: if the list were in order, equal values would sit next to each other, and one pass over neighbours would be enough.

python

def has_duplicate_naive(a):
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                return True
    return False

print(has_duplicate_naive([4, 1, 7, 1]))   # True
print(has_duplicate_naive([4, 1, 7, 2]))   # False

Cost: O(n²) comparisons: n × (n − 1) / 2.

Implementation

Python's sort

For almost everything, use the built-in sort. It is fast (O(n log n)), well tested and stable: items that compare equal keep their original relative order.

Plan in plain steps

pseudocode

sorted(items) returns a new sorted list; items.sort() sorts in place
key=f sorts by f(item); reverse=True sorts descending

python

words = ["pear", "fig", "apple", "kiwi"]
print(sorted(words))   # ['apple', 'fig', 'kiwi', 'pear']
print(sorted(words, key=len))   # ['fig', 'pear', 'kiwi', 'apple']
print(sorted([3, 1, 2], reverse=True))   # [3, 2, 1]

pairs = [(2, "b"), (1, "z"), (2, "a")]
print(sorted(pairs))   # [(1, 'z'), (2, 'a'), (2, 'b')]

scores = [("ana", 90), ("ben", 85), ("cy", 90)]
print(sorted(scores, key=lambda s: (-s[1], s[0])))   # [('ana', 90), ('cy', 90), ('ben', 85)]

Reading the code

›key=len sorts by length. pear and kiwi both have length 4 and stay in their original order (pear first): that is stability.
›Tuples compare element by element, so (2, 'a') comes before (2, 'b'): ties on the first element are broken by the second.
›key=lambda s: (-s[1], s[0]) sorts by score descending (the minus sign flips the order) and then by name ascending. Putting several criteria in a tuple is the standard multi-key idiom.
›sorted returns a new list and leaves the original alone; list.sort() changes the list in place and returns None (a common source of bugs).

Worked by hand

Bubble sort by hand

Sort [5, 2, 4, 1, 3]. Each pass compares neighbours from the left and stops one earlier than the last pass, since the right end is already in place.

pass	swaps in this pass	array afterwards
1	5↔2, 5↔4, 5↔1, 5↔3	[2, 4, 1, 3, 5]
2	4↔1, 4↔3	[2, 1, 3, 4, 5]
3	2↔1	[1, 2, 3, 4, 5]
4	none	[1, 2, 3, 4, 5]

1
Why it is O(n²)
Pass 1 does 4 comparisons, pass 2 does 3, then 2, then 1: n − 1 + … + 1 = n(n − 1)/2 comparisons, the same pair count as in the Complexity lesson.
2
Swaps count inversions
A swap fixes exactly one out-of-order pair. [5, 2, 4, 1, 3] has 7 such pairs, so 7 swaps.

Implementation

Three simple sorts you should be able to write

They are rarely the right tool in a contest, but they teach the ideas behind faster algorithms, and writing them builds fluency with indices and swaps.

python

def bubble_sort(a):
    a = a[:]
    for end in range(len(a) - 1, 0, -1):
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
    return a

def selection_sort(a):
    a = a[:]
    for i in range(len(a)):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]
    return a

def insertion_sort(a):
    a = a[:]
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

data = [5, 2, 4, 1, 3]
print(bubble_sort(data))   # [1, 2, 3, 4, 5]
print(selection_sort(data))   # [1, 2, 3, 4, 5]
print(insertion_sort(data))   # [1, 2, 3, 4, 5]
print(data)   # [5, 2, 4, 1, 3]

Reading the code

›Bubble: swap neighbours that are out of order; each pass settles the largest remaining value at the end.
›Selection: find the smallest remaining item and swap it into the next position. It always does n(n − 1)/2 comparisons but at most n − 1 swaps.
›Insertion: keep the left part sorted and slide each new item left into its place, like cards in a hand. It is very fast (O(n)) on already-sorted data, which is why real sorts use it for small pieces.
›Each starts with a = a[:] so the caller's list is left unchanged; the last print shows the original is intact.

Worked problem

Duplicates by sorting

The problem

Return True if any value appears at least twice in a list, in O(n log n) time.

Sort a copy of the list.
Compare each item with its right neighbour.
Any equal pair means a duplicate; if none, return False.

python

def has_duplicate(a):
    b = sorted(a)
    for i in range(1, len(b)):
        if b[i] == b[i - 1]:
            return True
    return False

print(has_duplicate([4, 1, 7, 1]))   # True
print(has_duplicate([4, 1, 7, 2]))   # False
print(has_duplicate([]))   # False

Takeaway. Sorting did the hard part: it made the question local. The naive O(n²) became O(n log n). (A set would give O(n) on average, which the Arrays and Hashing lessons cover.)

Worked problem

Merge overlapping intervals

The problem

Given intervals like [1, 3], [2, 6], [8, 10], [15, 18], merge all that overlap and return the result.

Sort the intervals by start. After that, any interval that overlaps the previous one must start before the previous one ends.
Keep a result list. For each interval: if it starts at or before the end of the last merged interval, extend that end; otherwise start a new merged interval.
Only the last merged interval ever needs checking, because earlier ones end before it starts.

python

def merge_intervals(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))   # [[1, 6], [8, 10], [15, 18]]
print(merge_intervals([[1, 4], [4, 5]]))   # [[1, 5]]

Takeaway. Sorting by start turns a two-dimensional overlap problem into a single left-to-right scan. max keeps the end correct when one interval is fully inside another.

Wrap-up

Remember this

Sorting makes hard questions local: equal and nearby values become neighbours.
Bubble, selection and insertion sort are O(n²); use them to learn, not to submit.
Python's built-in sort is O(n log n) and stable; use key and tuples for multi-criteria ordering.
list.sort() returns None; sorted returns a new list.
Reach for sorting with intervals, closest pairs, duplicates, greedy choices and before binary search.

Cheat sheet

Built-in: sorted(a) new list · a.sort() in place, returns None
Options: key=f, reverse=True; multi-key: key=lambda x: (-x[1], x[0])
Stable: equal keys keep their original order
Cost: built-in O(n log n); bubble/selection/insertion O(n²)
Why sort: adjacent duplicates, binary search, two pointers, intervals, greedy
Keep indices: sort (value, index) pairs

Top traps to avoid

Writing your own O(n²) sort for large inputs.
a = a.sort().
Wrong sign when sorting descending by one key and ascending by another.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.How many comparisons does bubble sort make on 5 items (no early exit)?
2.What does it mean that Python's sort is stable?
3.sorted([("ana", 90), ("ben", 85), ("cy", 90)], key=lambda s: (-s[1], s[0])) starts with:
4.Which problem is made easy by sorting first?
5.What is the value of b after b = [3, 1, 2].sort()?
6.For n = 100,000, roughly how many steps does an O(n²) sort take versus the built-in sort?
7.What does sorted(['b', 'A', 'c']) return?
8.What does sorted([(2, 'b'), (1, 'z'), (2, 'a')]) return?
9.For a = [3, 1, 2], what does sorted(a, key=lambda x: -x) return?
10.Why does sorting help when you check a list for duplicates?
11.What does print(sorted(['bb', 'a', 'ccc'], key=len)) print?
12.nums = [5, 2, 9]; nums.sort(reverse=True). What does print(nums[0]) print?
13.Why does sorting help find the closest pair of values?
14.Python's built-in sort on n items: what is the running time?
15.What does print(sorted([3, 1, 2])[1]) print?

Sorting Basics

After this lesson you will be able to

Sorting a hand of cards

Finding duplicates without ordering

Order puts equal and nearby values side by side

The vocabulary of sorting

Python's sort

Reading the code

Bubble sort in motion

Bubble sort by hand

Three simple sorts you should be able to write

Reading the code

Why the simple sorts are O(n²)

Edge cases

Mistakes to avoid

How to spot that sorting helps

Duplicates by sorting

Merge overlapping intervals

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up2 problems

Core4 problems

Application3 problems

Challenge1 problem