# Các giải thuật sắp xếp - P4: Merge

**1. Merge sort**
Merge sort hoạt động bằng cách chặt đôi mảng ra cho đến khi nó không thể nào được chặt nữa (recursively). Sau đó, nó sẽ ghép các phần tử đã bị chia đôi đó thành một mảng tăng. Bởi vì 2 mảng con trước đó đã được sắp xếp, nên việc ghép lại thành mảng tăng chỉ còn độ phức tạp O(n) (i.e so sánh 2 phần tử đầu của 2 mảng, cho phần tử nhỏ hơn vào mảng)

Mã giả:

function MergeSort(array):
    if length(array) <= 1:
        return array   // Base case: array with 0 or 1 element is already sorted

    // Split the array into two halves
    middle = length(array) / 2
    left_half = MergeSort(array[0...middle-1])
    right_half = MergeSort(array[middle...length(array)-1])

    // Merge the sorted halves
    return Merge(left_half, right_half)

function Merge(left_half, right_half):
    merged_array = []

    // Merge elements from left and right halves into a sorted array
    while length(left_half) > 0 and length(right_half) > 0:
        if left_half[0] <= right_half[0]:
            merged_array.append(left_half[0])
            left_half = left_half[1...length(left_half)-1]
        else:
            merged_array.append(right_half[0])
            right_half = right_half[1...length(right_half)-1]

    // Append remaining elements (if any) from left_half
    while length(left_half) > 0:
        merged_array.append(left_half[0])
        left_half = left_half[1...length(left_half)-1]

    // Append remaining elements (if any) from right_half
    while length(right_half) > 0:
        merged_array.append(right_half[0])
        right_half = right_half[1...length(right_half)-1]

    return merged_array

Độ phức tạp:
Worst time complexity: nlogn
Average time complexity: nlogn
Best time complexity: nlogn
Space complexity: n