🧩 Insertion Sort

Idea: Chèn từng phần tử vào đúng vị trí trong mảng đã sorted (giống xếp bài trên tay).

def insertionSort(arr):
    for i in range(1, len(arr)):
        j = i - 1
        while j >= 0 and arr[j + 1] < arr[j]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
            j -= 1
    return arr

# Example
arr = [4, 2, 1]
print(insertionSort(arr))  # [1, 2, 4]

Time: O(n²)

Space: O(1)

⚙️ Merge Sort

Idea: Chia đôi → sort từng nửa → merge lại (Divide and Conquer).

def mergeSort(arr, s, e):
    if e - s + 1 <= 1:
        return arr
    m = (s + e) // 2
    mergeSort(arr, s, m)
    mergeSort(arr, m + 1, e)
    merge(arr, s, m, e)
    return arr

def merge(arr, s, m, e):
    L = arr[s:m+1]
    R = arr[m+1:e+1]
    i = j = 0
    k = s
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            arr[k] = L[i]; i += 1
        else:
            arr[k] = R[j]; j += 1
        k += 1
    while i < len(L):
        arr[k] = L[i]; i += 1; k += 1
    while j < len(R):
        arr[k] = R[j]; j += 1; k += 1

# Example
arr = [5, 2, 8, 1]
print(mergeSort(arr, 0, len(arr)-1))  # [1, 2, 5, 8]

Time: O(n log n)

Space: O(n)

⚡ Quick Sort

Idea: Chọn pivot → chia mảng thành hai phần → đệ quy sort từng phần.

def quickSort(arr, s, e):
    if e - s + 1 <= 1:
        return arr
    pivot = arr[e]
    left = s
    for i in range(s, e):
        if arr[i] < pivot:
            arr[left], arr[i] = arr[i], arr[left]
            left += 1
    arr[e], arr[left] = arr[left], arr[e]
    quickSort(arr, s, left - 1)
    quickSort(arr, left + 1, e)
    return arr

# Example
arr = [3, 6, 1, 4]
print(quickSort(arr, 0, len(arr)-1))  # [1, 3, 4, 6]

Time: O(n log n) average, O(n²) worst

Space: O(log n)

🎨 Bucket Sort (Counting Sort cho 0,1,2)

Idea: Đếm số lượng phần tử rồi ghi lại theo thứ tự.