Sorting Algorithms

30 min In Progress

Learning Objectives

  • Explain the core idea of Bubble, Insertion, Merge, and Quick Sort in one sentence each
  • Pick the right algorithm for a given scenario using the complexity table
  • Use Python's built-in sorted() with a lambda key to rank security alerts

The Algorithm Landscape

Eight sorting algorithms are in common use. You don't need to implement all of them in production — Python's sorted() uses Timsort (a merge+insertion hybrid) and is faster than anything you'll write by hand. But understanding the algorithms tells you why Timsort beats Bubble Sort by orders of magnitude, and which tradeoffs matter when Timsort isn't available. One-liner for each: Bubble — repeatedly swap neighbours if out of order. Selection — find the minimum remaining, place it next. Insertion — take one item at a time, insert into correct spot. Merge — split in half, sort each half, merge back together. Quick — pick a pivot; smaller left, larger right; recurse. Heap — use a binary heap to pull the largest item repeatedly. Bucket — scatter into value-range buckets, sort each bucket. Radix — sort digit by digit, least significant first.

# Algorithm comparison table
algorithms = [
    ('Bubble',    'O(n²)',    'O(n²)',    'O(1)',   'Yes', 'teaching only'),
    ('Insertion', 'O(n)',     'O(n²)',    'O(1)',   'Yes', 'great for nearly-sorted'),
    ('Merge',     'O(n logn)','O(n logn)','O(n)',  'Yes', 'reliable, predictable'),
    ('Quick',     'O(n logn)','O(n²)',    'O(logn)','No', 'fastest in practice'),
    ('Heap',      'O(n logn)','O(n logn)','O(1)',   'No', 'good when memory limited'),
    ('Radix',     'O(nk)',    'O(nk)',    'O(n+k)', 'Yes','great for fixed-width ints'),
    ('Timsort',   'O(n)',     'O(n logn)','O(n)',   'Yes','Python built-in default'),
]

print(f'{'Algorithm':10} {'Best':10} {'Worst':10} {'Space':8} {'Stable':7} Notes')
print('-' * 70)
for row in algorithms:
    print(f'{row[0]:10} {row[1]:10} {row[2]:10} {row[3]:8} {row[4]:7} {row[5]}')

Merge Sort — Reliable O(n log n)

Merge sort is the go-to for guaranteed performance. It always runs in O(n log n) — unlike Quick Sort which degrades to O(n²) in the worst case. The tradeoff is O(n) extra memory. Good for sorting event logs or timestamps where predictability matters more than squeezing the last bit of speed.

class merge_sorter:
    def sort(self, items):
        arr = items.copy()
        self._merge_sort(arr, 0, len(arr) - 1)
        return arr

    def _merge_sort(self, arr, left, right):
        if left < right:
            mid = (left + right) // 2
            self._merge_sort(arr, left, mid)
            self._merge_sort(arr, mid + 1, right)
            self._merge(arr, left, mid, right)

    def _merge(self, arr, left, mid, right):
        left_part = arr[left:mid + 1]
        right_part = arr[mid + 1:right + 1]
        i = j = 0
        k = left
        while i < len(left_part) and j < len(right_part):
            if left_part[i] <= right_part[j]:
                arr[k] = left_part[i]
                i += 1
            else:
                arr[k] = right_part[j]
                j += 1
            k += 1
        while i < len(left_part):
            arr[k] = left_part[i]
            i += 1
            k += 1
        while j < len(right_part):
            arr[k] = right_part[j]
            j += 1
            k += 1


# Security example: sort event log timestamps
event_timestamps = [1620, 1500, 1800, 1430, 1700, 1550]
sorted_events = merge_sorter().sort(event_timestamps)
print('Event log sorted chronologically:')
print(sorted_events)

Python Built-in Sorting — What to Use in Real Scripts

In production Python you almost never implement a sorting algorithm by hand. sorted() and list.sort() use Timsort — a highly optimized merge+insertion hybrid. It's stable, O(n log n) average/worst, and O(n) on nearly-sorted data (very common in logs). The real skill is knowing how to use the key parameter to sort by any attribute of complex objects.

class security_alert:
    def __init__(self, name, severity, cvss_score, timestamp):
        self.name = name
        self.severity = severity
        self.cvss_score = cvss_score
        self.timestamp = timestamp

    def __repr__(self):
        return f'{self.name}({self.severity}, cvss={self.cvss_score})'


alerts = [
    security_alert('brute-force',    'high',     7.5, 1003),
    security_alert('port-scan',      'low',      2.1, 1001),
    security_alert('malware-beacon', 'critical', 9.8, 1002),
    security_alert('sql-injection',  'high',     8.2, 1000),
    security_alert('weak-cipher',    'medium',   4.0, 1004),
]

# Sort by CVSS score descending — highest risk first
by_risk = sorted(alerts, key=lambda a: a.cvss_score, reverse=True)
print('Alerts by CVSS risk (highest first):')
for a in by_risk:
    print(f'  cvss {a.cvss_score:4.1f}  {a.severity:8}  {a.name}')

# Sort by timestamp to reconstruct the event timeline
by_time = sorted(alerts, key=lambda a: a.timestamp)
print('\nAlert timeline:')
for a in by_time:
    print(f'  t={a.timestamp}  {a.name}')

📝 Exercise: Vulnerability Triage Sorter

Given a list of vulnerabilities (each with a name, cvss_score, and affected_hosts count), sort them two ways: first by cvss_score descending, then by a combined risk_score (cvss_score * affected_hosts) descending. Print both sorted lists and notice how the ranking changes when host count is factored in.

code.py
Output

            

        

    


    

        ← Back to Chapter