Merge Sort (Sắp xếp trộn)

Merge Sort tuân theo quy tắc Divide and Conquer (Chia để trị) để sắp xếp một tập hợp số/phần tử nhất định theo phương pháp đệ quy, do đó tiêu tốn ít thời gian thực thi hơn.

Trong các bài viết trước về Bubble Sort, Insertion SortSelection Sort, cả 3 đều có thời gian chạy trong trường hợp xấu nhất là O(n2). Khi kích thước đầu vào tăng lên, cả 3 giải thuật này có thể mất nhiều thời gian để chạy.

Merge Sort có thời gian thực thi trong tất cả các trường hợp là O(n log n). Trước khi tìm hiểu cơ chế hoạt động và cách cài đặt Merge Sort, chúng ta hãy tìm hiểu quy tắc Divide and Conquer là gì?

Bạn đang đọc: Merge Sort (Sắp xếp trộn)

1. Divide and Conquer

Trong khoa học máy tính, divide and conquer là một quy mô phong cách thiết kế thuật toán dựa trên đệ quy nhiều nhánh ( multi-branched recursion ) .

Nếu chúng ta có thể chia tách một bài toán lớn (a single big problem) thành các bài toán nhỏ hơn (smaller sub-problems) cho đến khi những bài toán nhỏ này trở nên đủ đơn giản để được giải quyết trực tiếp. Chúng ta sẽ giải quyết từng bài toán nhỏ, sau đó kết hợp các kết quả của chúng lại để tìm ra kết quả của bài toán lớn ban đầu, thì việc giải quyết bài toán lớn sẽ trở nên dễ dàng hơn.

Đọc thêm: https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

Trong giải thuật Merge Sort, một mảng gồm n phần tử chưa được sắp xếp, sẽ được chia tách thành n mảng con, mỗi mảng gồm 1 phần tử. Vì chỉ có 1 phần tử nên các mảng con được coi như đã được sắp xếp. Sau đó, chúng ta sẽ liên tục hợp nhất các tập hợp con này, để tạo ra các tập hợp con mới được sắp xếp và cuối cùng chúng ta sẽ tạo ra được một mảng được sắp xếp hoàn chỉnh.

Quy tắc Divide and Conquer bao gồm 3 bước:

  1. Divide (chia) một vấn đề lớn thành nhiều vấn đề nhỏ.
  2. Conquer (giải quyết) các vấn đề nhỏ.
  3. Combine (kết hợp) các kết quả của các vấn đề nhỏ để tìm ra kết quả cho vấn đề lớn ban đầu.

Image Source: Studytonight

2. Cơ chế hoạt động của Merge Sort

Như để thảo luận ở trên, Merge Sort sử dụng quy tắc Divide and Conquer trong vấn đề sắp xếp một mảng đã cho. Chúng ta sẽ chia mảng ban đầu ở vị trí giữa mảng (middle) thành các mảng con.

Ví dụ mảng ban đầu có 6 phần tử, chúng ta sẽ chia tách thành 2 mảng con với 3 phần tử mỗi mảng. Nhưng đến đây thì chúng ta vẫn chưa thể sắp xếp được mảng ban đầu, nên ta sẽ tiếp tục chia tách thành các mảng con sao cho cuối cùng mỗi mảng con chỉ có duy nhất 1 phần tử. Đến đây thì chúng ta đã thành công trong việc chia một vấn đề lớn thành các vấn đề nhỏ đủ để giải quyết trực tiếp. Cuối cùng chúng ta sẽ hợp nhất các mảng con này lại từng bước để tạo ra được một mảng sắp xếp hoàn chỉnh.

Lấy ví dụ một mảng với các giá trị {14, 7, 3, 12, 9, 11, 6, 2}. Hình ảnh dưới đây mô tả cách sắp xếp lại mảng theo giải thuật Merge Sort:

Image Source: Studytonight

3. Cài đặt Merge Sort

Mã code dưới đây sẽ mô tả cách cài đặt giải thuật Merge Sort trong Java:

MergeSort

package com.icancodeit.algorithm.sorting;

import java.util.Arrays;

public class MergeSort {

  // Sort the original data
  private static final int[] NUMBERS = {14, 7, 3, 12, 9, 11, 6, 2};

  private static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
      int mid = (left + right) / 2;
      mergeSort(arr, left, mid);
      mergeSort(arr, mid + 1, right);
      merge(arr, left, mid, right);
    }
  }

  private static void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] L = new int[n1];
    int[] R = new int[n2];

    for (int i = 0; i < n1; i++) {
      L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
      R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2) {
      if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
      } else {
        arr[k] = R[j];
        j++;
      }
      k++;
    }

    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

    while (j < n2) {
      arr[k] = R[j];
      j++;
      k++;
    }
  }

  public static void main(String[] args) {
    mergeSort(NUMBERS, 0, NUMBERS.length - 1);
    System.out.println(Arrays.toString(NUMBERS) + " mergeSort");
  }

}

Kết quả

[2, 3, 6, 7, 9, 11, 12, 14] mergeSort

4. Phân tích độ phức tạp của Merge Sort

  • Time Complexity: O(n log n)
  • Space Complexity: O(n)

Đọc thêm:

https://www.studytonight.com/data-structures/merge-sort
https://github.com/amejiarosario/