Sorting เชิงลึก

# bubble sort: สลับคู่ที่อยู่ผิดที่ ไล่ไปเรื่อย ๆ
def bubble_sort(arr):
    arr = arr[:]
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([5, 2, 8, 1]))   # [1, 2, 5, 8]

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # เรียงครึ่งซ้าย
    right = merge_sort(arr[mid:])   # เรียงครึ่งขวา
    return merge(left, right)       # รวมแบบเรียง

def merge(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:]); result.extend(b[j:])
    return result

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