Merge Sorted Arrays: gộp hai mảng đã sắp xếp

Cho hai mảng số nguyên a và b, mỗi mảng đã sắp xếp tăng dần. Trả về một mảng mới chứa mọi phần tử của cả hai, vẫn sắp xếp tăng dần.

Đầu vào: a = [1, 3, 5], b = [2, 4, 6, 8]
Đầu ra:  [1, 2, 3, 4, 5, 6, 8]

Trong game: hai server gộp làm một. Bảng xếp hạng của mỗi server đã sắp theo điểm, cần ghép thành một bảng chung mà không phải sắp xếp lại từ đầu.

Cách dễ nghĩ: nối rồi sắp xếp lại

Đổ cả hai mảng vào một mảng rồi gọi hàm sắp xếp có sẵn. C# 12 có cú pháp [..a, ..b] để nối mảng.

int[] Merge(int[] a, int[] b)
{
    int[] all = [..a, ..b];
    Array.Sort(all);
    return all;
}

def merge(a, b):
    return sorted(a + b)

Độ phức tạp: thời gian O((n + m) log(n + m)), với n và m là độ dài hai mảng. Code đúng, nhưng bỏ phí việc hai mảng đã được sắp xếp sẵn.

Cách nhanh: hai con trỏ

Phần tử nhỏ nhất của kết quả chắc chắn là a[0] hoặc b[0]. Lấy cái nhỏ hơn, dời con trỏ bên đó lên một ô, rồi lại so hai phần tử đang đứng đầu. Giống hai hàng người chơi đứng trước cổng: trọng tài chỉ cần nhìn hai người đứng đầu hai hàng.

Khi một mảng đã hết, phần còn lại của mảng kia chép thẳng vào cuối, vì nó đã sắp xếp sẵn và lớn hơn mọi thứ đã lấy.

int[] Merge(int[] a, int[] b)
{
    var result = new int[a.Length + b.Length];
    int i = 0, j = 0, k = 0;
    while (i < a.Length && j < b.Length)
    {
        if (a[i] <= b[j]) result[k++] = a[i++];
        else result[k++] = b[j++];
    }
    while (i < a.Length) result[k++] = a[i++];
    while (j < b.Length) result[k++] = b[j++];
    return result;
}

def merge(a, b):
    result = []
    i = j = 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

result[k++] = a[i++] trong C# nghĩa là: gán a[i] vào result[k], rồi tăng cả i và k thêm 1.

Chạy tay với a = [1, 3, 5], b = [2, 4, 6, 8]:

Độ phức tạp: thời gian O(n + m) vì mỗi phần tử được lấy đúng một lần, bộ nhớ O(n + m) cho mảng kết quả.

Dùng <= thay vì < khi so sánh giúp hai phần tử bằng nhau giữ đúng thứ tự: phần tử của a đứng trước. Tính chất này gọi là sắp xếp ổn định, rất quan trọng khi hai người chơi bằng điểm và người của server A đăng ký trước.

Lỗi hay gặp: quên hai vòng lặp chép phần còn lại. Vòng lặp chính dừng ngay khi một mảng hết, nên số 6 và 8 ở ví dụ trên sẽ biến mất. Bản C# không báo lỗi gì cả, chỉ trả về mảng có hai số 0 ở cuối, vì mảng int mới tạo mặc định toàn số 0. Lỗi kiểu này rất khó thấy nếu không chạy thử.

Khi đi phỏng vấn

• Gộp hai mảng đã sắp xếp là bước chính của Merge Sort. Biết bài này thì chỉ còn thiếu phần chia đôi mảng là viết được Merge Sort.
• Hỏi lại đề: trả về mảng mới hay phải gộp tại chỗ vào một trong hai mảng? Phiên bản gộp tại chỗ nằm ngay ở bài tập dưới đây.

Bài tập

Mảng nums1 có độ dài m + n: m phần tử đầu đã sắp xếp, n ô cuối là 0 để chừa chỗ. Mảng nums2 có n phần tử đã sắp xếp. Gộp nums2 vào nums1 tại chỗ, không tạo mảng mới.

Đầu vào: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
Sau khi gọi: nums1 = [1, 2, 2, 3, 5, 6]

void MergeInPlace(int[] nums1, int m, int[] nums2, int n)
{
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0)
    {
        if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
        else nums1[k--] = nums2[j--];
    }
}

def merge_in_place(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1