Merge sort: dela, sortera, sammanfoga

# High-level merge sort structure
def merge_sort(arr):
    # Base case: 0 or 1 element already sorted
    if len(arr) <= 1:
        return arr
    # Divide
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])   # sort left half
    right = merge_sort(arr[mid:])   # sort right half
    # Conquer (merge)
    return merge(left, right)

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= preserves stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]

def merge_sort_full(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort_full(arr[:mid])
    right = merge_sort_full(arr[mid:])
    # Merge the two sorted halves
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]: merged.append(left[i]);  i += 1
        else:                   merged.append(right[j]); j += 1
    merged.extend(left[i:] + right[j:])
    return merged

print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]

# Trace the tree depth
level_work = []

def merge_sort_traced(arr, depth=0):
    if depth >= len(level_work):
        level_work.append(0)
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort_traced(arr[:mid],  depth+1)
    right = merge_sort_traced(arr[mid:],  depth+1)
    level_work[depth] += len(arr)  # track merge work
    merged = sorted(left + right)  # simplified merge
    return merged

merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
    print(f'Level {d}: {work} elements merged')

# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
    n = len(arr)
    width = 1
    while width < n:
        for i in range(0, n, 2 * width):
            left  = arr[i:i+width]
            right = arr[i+width:i+2*width]
            # Merge and put back
            merged = []
            a, b = 0, 0
            while a < len(left) and b < len(right):
                if left[a] <= right[b]: merged.append(left[a]);  a+=1
                else:                   merged.append(right[b]); b+=1
            merged += left[a:] + right[b:]
            arr[i:i+len(merged)] = merged
        width *= 2
    return arr

print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]

# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items)  # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)

import heapq

def merge_k_sorted(arrays):
    result = []
    heap = []
    # Push first element from each array with array index
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    while heap:
        val, arr_i, elem_i = heapq.heappop(heap)
        result.append(val)
        if elem_i + 1 < len(arrays[arr_i]):
            next_val = arrays[arr_i][elem_i + 1]
            heapq.heappush(heap, (next_val, arr_i, elem_i+1))
    return result

arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs))  # [1,2,3,4,5,6,7,8,9]

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left,  l_inv = count_inversions(arr[:mid])
    right, r_inv = count_inversions(arr[mid:])
    merged = []
    inversions = l_inv + r_inv
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            inversions += len(left) - i  # all remaining left elements > right[j]
    merged.extend(left[i:] + right[j:])
    return merged, inversions

_, inv = count_inversions([3, 1, 2])
print(inv)  # 2: (3,1) and (3,2)

# Head-to-head complexity comparison:
# Algorithm     | Best  | Avg      | Worst  | Space  | Stable
# Bubble sort   | O(n)  | O(n^2)   | O(n^2) | O(1)   | Yes
# Insertion sort| O(n)  | O(n^2)   | O(n^2) | O(1)   | Yes
# Merge sort    | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort    | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort     | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No

print('Merge sort: stable, O(n log n) guaranteed, O(n) space')

# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
    chunks = []
    for i in range(0, len(data), chunk_size):
        chunk = sorted(data[i:i+chunk_size])  # sort in-memory
        chunks.append(chunk)
    print(f'Created {len(chunks)} sorted chunks')
    # Merge all chunks
    import heapq
    heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
    heapq.heapify(heap)
    result = []
    while heap:
        val, ci, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(chunks[ci]):
            heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
    return result

print(external_sort(list(range(20,0,-1)), 5)[:10])

# One-shot merge sort for interview clarity:
def ms(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: res.append(l[i]); i+=1
        else:             res.append(r[j]); j+=1
    return res + l[i:] + r[j:]

print(ms([5,2,4,6,1,3]))  # [1,2,3,4,5,6]