Merge Sort — Interview Preparation¶

def merge_sort(arr):
    if len(arr) <= 1:
        return list(arr)
    mid = len(arr) // 2
    return _merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

def _merge(l, r):
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            out.append(l[i]); i += 1
        else:
            out.append(r[j]); j += 1
    out += l[i:]
    out += r[j:]
    return out

print(merge_sort([5, 2, 8, 1, 9, 3, 7, 4]))

def count_inversions(arr):
    aux = [0] * len(arr)
    return _sort_count(arr, aux, 0, len(arr) - 1)

def _sort_count(a, aux, lo, hi):
    if lo >= hi: return 0
    mid = (lo + hi) // 2
    count = _sort_count(a, aux, lo, mid) + _sort_count(a, aux, mid + 1, hi)
    count += _merge_count(a, aux, lo, mid, hi)
    return count

def _merge_count(a, aux, lo, mid, hi):
    for k in range(lo, hi + 1): aux[k] = a[k]
    i, j, count = lo, mid + 1, 0
    for k in range(lo, hi + 1):
        if i > mid:                 a[k] = aux[j]; j += 1
        elif j > hi:                a[k] = aux[i]; i += 1
        elif aux[i] <= aux[j]:      a[k] = aux[i]; i += 1
        else:
            a[k] = aux[j]; j += 1
            count += mid - i + 1
    return count

print(count_inversions([5, 4, 3, 2, 1]))  # 10
print(count_inversions([2, 4, 1, 3, 5]))  # 3

import heapq

class ListNode:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt

def merge_k_lists(lists):
    heap = []
    # Initialize heap with first node from each list
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    dummy = ListNode()
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

class ListNode:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt

def sort_list(head):
    if not head or not head.next:
        return head
    # Find midpoint
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    # Recursively sort halves
    left  = sort_list(head)
    right = sort_list(mid)
    return merge_two_lists(left, right)

def merge_two_lists(l, r):
    dummy = ListNode()
    tail = dummy
    while l and r:
        if l.val <= r.val:
            tail.next = l; l = l.next
        else:
            tail.next = r; r = r.next
        tail = tail.next
    tail.next = l or r
    return dummy.next

# Phase 1
def chunk_and_sort(input_file, chunk_size_mb=100):
    chunk_size = chunk_size_mb * 1_000_000 // 4  # int = 4 bytes
    runs = []
    with open(input_file) as f:
        chunk = []
        for line in f:
            chunk.append(int(line))
            if len(chunk) >= chunk_size:
                chunk.sort()
                runs.append(write_run(chunk))
                chunk = []
        if chunk:
            chunk.sort()
            runs.append(write_run(chunk))
    return runs

# Phase 2
import heapq
def merge_runs(run_paths, output_path):
    iterators = [iter_file(p) for p in run_paths]
    with open(output_path, 'w') as out:
        for val in heapq.merge(*iterators):
            out.write(f"{val}\n")