D&A Sorting

Merge Sort

Merge sort is a divide-and-conquer algorithm that recursively splits an array into halves, sorts each half, and then merges the sorted halves back together. It has stable and predictable performance.

Space: O(n log n)
Time:   O(n)


def merge(left, right):
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    if i < len(left):
        res.extend(left[i:])
    else:
        res.extend(right[j:])
    return res

# >>> merge([1,2], [3, 4])
# [1, 2, 3, 4]

def sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = sort(arr[:mid])
    right = sort(arr[mid:])
    return merge(left, right)

>>> sort([5, 1, 3, 4, 2])
# [1, 2, 3, 4, 5]

Topological Sort

G 0 0 1 1 0->1 2 2 1->2 3 3 2->3

Topological sort is an ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u->v, vertex u appears before vertex v in the ordering. It is used for dependency resolution, such as task scheduling, where certain tasks must be completed before others.

Space: O(n log n)
Time:   O(n)


N = 4  # number of nodes

edges = [[1,0], [2,1], [3,2]]
adj = {x: [] for x in range(N)}

for x, y in edges:
    adj[x].append(y)

def topological(adj):
    visited = [0] * N
    order = []
    def dfs(node):
        if visited[node] == 2:  # visited
            return True
        if visited[node] == 1:  # cycle
            return False
        visited[node] = 1  # visiting
        for neighbor in adj[node]:
            if not dfs(neighbor):
                return False
        visited[node] = 2
        order.append(node)
        return True
    for node in range(N):
        if not dfs(node):
            raise Exception('cycle detected')
    return order

# >>> topological(adj)
# [0, 1, 2, 3]