Tìm hiểu thuật toán sắp xếp trộn (Merge Sort)

• Bước 1: Xác định điểm đứng giữa danh sách.
• Bước 2: Từ điểm đứng giữa đó tách danh sách thành hai phần bằng nhau (hoặc gần bằng nhau)
• Bước 3: Dùng đệ quy để tiếp tục bẻ đôi các nửa này cho đến khi chỉ còn duy nhất một phần tử.
• Bước 4: Ghép các phần tử đã bẻ đôi lại với nhau theo thứ tự tăng dần hoặc giảm dần.

• Đầu tiên ta nhận mảng đầu vào, sau đó bẻ mảng ra làm đôi tại vị trí chia cắt mảng.

• Ta tiếp tục tách các mảnh nhỏ ra thành các mảnh nhỏ hơn.

• Bây giờ ta có các mảng chỉ có duy nhất một phần tử. Tiếp theo ta sẽ so sánh các mảnh và ghép chúng vào mảng đã được sắp xếp. Cách làm khá đơn giản, các bạn hãy tưởng tượng có 10 mẫu giấy đánh số từ 1 đến 10 và việc của bạn là ghép chúng lại sao cho các bạn được một dãy số đã sắp xếp tăng dần từ 1 đến 10, các bạn làm sao? Đơn giản là phần tử nào nhỏ hơn sẽ được ghép vào. Thuật toán này cũng tương tự như vậy.

#include <stdio.h>

// Hàm xuất mảng
void printArr(int arr[], int arrLength)
{
    for (int i = 0; i < arrLength; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void merge(int arr[], int leftArr[], int rightArr[], int leftLength, int rightLength);

// Hàm sắp xếp
void mergeSort(int arr[], int arrLength)
{
    // Cho một cái base case vì đây là hàm đệ quy
    if (arrLength <= 1)
    {
        return;
    }
    
    // Tạo hai mảng phụ để lưu trữ hai mảnh đã bẻ đôi
    int mid = arrLength / 2; // Xác định vị trí để chia cắt
    int leftLength = mid, rightLength = arrLength - mid; // Độ dài hai nửa
    int leftArr[leftLength];
    int rightArr[rightLength];

    // Đưa các phần tử từ mảng gốc vào hai mảng phụ
    int rightIndex = 0;
    for (int i = 0; i < arrLength; i++)
    {
        // Phần bên trái vị trí chia cắt (i < mid) được đưa vào mảng leftArr
        if (i < mid)
        {
            leftArr[i] = arr[i];
        }
        // Phần bên phải vị trí chia cắt (i >= mid) được đưa vào mảng rightArr
        else
        {
            rightArr[rightIndex] = arr[i];
            rightIndex++
        }
    }

    // Gọi đệ quy để tiếp tục sắp xếp
    mergeSort(leftArr, leftLength);
    mergeSort(rightArr, rightLength);

    // Gọi hàm merge để ghép hai mảnh lại với nhau thành mảng đã được sắp xếp
    merge(arr, leftArr, rightArr, leftLength, rightLength);
}

// Hàm để ghép các mảnh lại với nhau
void merge(int arr[], int leftArr[], int rightArr[], int leftLength, int rightLength) {
    int leftIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên trái
    int rightIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên phải
    int i = 0; // Biến giữ vị trí tiếp theo được ghép vào ở mảng arr

    // Vòng lặp while để so sánh và ghép các phần tử lại với nhau
    while (leftIndex < leftLength && rightIndex < rightLength)
    {
        // Phần tử nào nhỏ hơn thì ghép vào
        if (leftArr[leftIndex] < rightArr[rightIndex])
        {
            arr[i] = leftArr[leftIndex];
            leftIndex++;
        }
        else
        {
            arr[i] = rightArr[rightIndex];
            rightIndex++;
        }
        i++;
    }
    
    // Ghép các phần tử dư thừa vào mảng arr nếu có
    while (leftIndex < leftLength)
    {
        arr[i] = leftArr[leftIndex];
        leftIndex++;
        i++;
    }
    
    while (rightIndex < rightLength)
    {
        arr[i] = rightArr[rightIndex];
        rightIndex++;
        i++;
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {45, 12, 48, 19, 36, 14, 30, 69};
    int arrLength = sizeof(arr) / sizeof(arr[0]);
    
    printf("Mang ban dau: ");
    printArr(arr, arrLength);

    mergeSort(arr, arrLength);

    printf("Mang da duoc sap xep: ");
    printArr(arr, arrLength);

    return 0;
}

#include <iostream>

using namespace std;

// Hàm xuất mảng
void printArr(int arr[], int arrLength)
{
    for (int i = 0; i < arrLength; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void merge(int arr[], int leftArr[], int rightArr[], int leftLength, int rightLength);

// Hàm sắp xếp
void mergeSort(int arr[], int arrLength)
{
    // Cho một cái base case vì đây là hàm đệ quy
    if (arrLength <= 1)
    {
        return;
    }
    
    // Tạo hai mảng phụ để lưu trữ hai mảnh đã bẻ đôi
    int mid = arrLength / 2; // Xác định vị trí để chia cắt
    int leftLength = mid, rightLength = arrLength - mid; // Độ dài hai nửa
    int leftArr[leftLength];
    int rightArr[rightLength];

    // Đưa các phần tử từ mảng gốc vào hai mảng phụ
    int rightIndex = 0;
    for (int i = 0; i < arrLength; i++)
    {
        // Phần bên trái vị trí chia cắt (i < mid) được đưa vào mảng leftArr
        if (i < mid)
        {
            leftArr[i] = arr[i];
        }
        // Phần bên phải vị trí chia cắt (i >= mid) được đưa vào mảng rightArr
        else
        {
            rightArr[rightIndex] = arr[i];
            rightIndex++
        }
    }

    // Gọi đệ quy để tiếp tục sắp xếp
    mergeSort(leftArr, leftLength);
    mergeSort(rightArr, rightLength);

    // Gọi hàm merge để ghép hai mảnh lại với nhau thành mảng đã được sắp xếp
    merge(arr, leftArr, rightArr, leftLength, rightLength);
}

// Hàm để ghép các mảnh lại với nhau
void merge(int arr[], int leftArr[], int rightArr[], int leftLength, int rightLength) {
    int leftIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên trái
    int rightIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên phải
    int i = 0; // Biến giữ vị trí tiếp theo được ghép vào ở mảng arr

    // Vòng lặp while để so sánh và ghép các phần tử lại với nhau
    while (leftIndex < leftLength && rightIndex < rightLength)
    {
        // Phần tử nào nhỏ hơn thì ghép vào
        if (leftArr[leftIndex] < rightArr[rightIndex])
        {
            arr[i] = leftArr[leftIndex];
            leftIndex++;
        }
        else
        {
            arr[i] = rightArr[rightIndex];
            rightIndex++;
        }
        i++;
    }
    
    // Ghép các phần tử dư thừa vào mảng arr nếu có
    while (leftIndex < leftLength)
    {
        arr[i] = leftArr[leftIndex];
        leftIndex++;
        i++;
    }
    
    while (rightIndex < rightLength)
    {
        arr[i] = rightArr[rightIndex];
        rightIndex++;
        i++;
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {45, 12, 48, 19, 36, 14, 30, 69};
    int arrLength = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Mang ban dau: ";
    printArr(arr, arrLength);

    mergeSort(arr, arrLength);

    cout << "Mang da duoc sap xep: ";
    printArr(arr, arrLength);

    return 0;
}

using System;

namespace Main 
{
    class Program
    {
        // Phương thức xuất mảng
        static void printArr(int[] arr)
        {
            foreach (int i in arr)
            {
                Console.Write($"{i} ");
            }
            Console.WriteLine();
        }
        
        // Phương thức sắp xếp
        static void mergeSort(int[] arr)
        {
            // Cho một cái base case vì đây là hàm đệ quy
            if (arr.Length <= 1)
            {
                return;
            }
            
            // Tạo hai mảng phụ để lưu trữ hai mảnh đã bẻ đôi
            int mid = arr.Length / 2; // Xác định vị trí để chia cắt
            int[] leftArr = new int[mid];
            int[] rightArr = new int[arr.Length - mid];
            
            // Đưa các phần tử từ mảng gốc vào hai mảng phụ
            int rightIndex = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                // Phần bên trái vị trí chia cắt (i < mid) được đưa vào mảng leftArr
                // Phần bên phải vị trí chia cắt (i >= mid) được đưa vào mảng rightArr
                if (i < mid)
                {
                    leftArr[i] = arr[i];
                }
                else
                {
                    rightArr[rightIndex] = arr[i];
                    rightIndex++;
                }
            }
            
            // Gọi đệ quy để tiếp tục sắp xếp
            mergeSort(leftArr);
            mergeSort(rightArr);
            
            // Gọi hàm merge để ghép hai mảnh lại với nhau thành mảng đã được sắp xếp
            merge(arr, leftArr, rightArr);
        }
        
        // Phương thức để ghép các mảnh lại với nhau
        static void merge(int[] arr, int[] leftArr, int[] rightArr)
        {
            int leftIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên trái
            int rightIndex = 0;// Biến giữ vị trí phần tử được so sánh ở mảnh bên phải
            int i = 0; // Biến giữ vị trí tiếp theo được ghép vào ở mảng arr
            
            // Vòng lặp while để so sánh và ghép các phần tử lại với nhau
            while (leftIndex < leftArr.Length && rightIndex < rightArr.Length)
            {
                // Phần tử nào nhỏ hơn thì ghép vào
                if (leftArr[leftIndex] < rightArr[rightIndex])
                {
                    arr[i] = leftArr[leftIndex];
                    leftIndex++;
                }
                else
                {
                    arr[i] = rightArr[rightIndex];
                    rightIndex++;
                }
                i++;
            }
            
            // Ghép các phần tử dư thừa vào mảng arr nếu có
            while (leftIndex < leftArr.Length)
            {
                arr[i] = leftArr[leftIndex];
                leftIndex++;
                i++;
            }
            
            while (rightIndex < rightArr.Length)
            {
                arr[i] = rightArr[rightIndex];
                rightIndex++;
                i++;
            }
        }
        
        static void Main()
        {
            int[] arr = {45, 12, 48, 19, 36, 14, 30, 69};
            
            Console.Write("Mang ban dau: ");
            printArr(arr);
            
            mergeSort(arr);
            
            Console.Write("Mang da duoc sap xep: ");
            printArr(arr);
        }
    }
}

import java.util.Arrays;

public class Main {
    // Phương thức sắp xếp
    public static void mergeSort(int[] arr) {
        // Cho một cái base case vì đây là hàm đệ quy
        if (arr.length <= 1) {
            return;
        }

        // Tạo hai mảng phụ để lưu trữ hai mảnh đã bẻ đôi
        int mid = arr.length / 2;
        int[] leftArr = new int[mid];
        int[] rightArr = new int[arr.length - mid];

        // Đưa các phần tử từ mảng gốc vào hai mảng phụ
        int rightIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            // Phần bên trái vị trí chia cắt (i < mid) được đưa vào mảng leftArr
            // Phần bên phải vị trí chia cắt (i >= mid) được đưa vào mảng rightArr
            if (i < mid) {
                leftArr[i] = arr[i];
            } else {
                rightArr[rightIndex] = arr[i];
                rightIndex++;
            }
        }

        // Gọi đệ quy để tiếp tục sắp xếp
        mergeSort(leftArr);
        mergeSort(rightArr);

        // Gọi hàm merge để ghép hai mảnh lại với nhau thành mảng đã được sắp xếp
        merge(arr, leftArr, rightArr);
    }

    // Phương thức để ghép các mảnh lại với nhau
    private static void merge(int[] arr, int[] leftArr, int[] rightArr) {
        int leftIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên trái
        int rightIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên phải
        int i = 0; // Biến giữ vị trí tiếp theo được ghép vào ở mảng arr

        // Vòng lặp while để so sánh và ghép các phần tử lại với nhau
        while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
            // Phần tử nào nhỏ hơn thì ghép vào
            if (leftArr[leftIndex] < rightArr[rightIndex]) {
                arr[i] = leftArr[leftIndex];
                leftIndex++;
            } else {
                arr[i] = rightArr[rightIndex];
                rightIndex++;
            }
            i++;
        }

        // Ghép các phần tử dư thừa vào mảng arr nếu có
        while (leftIndex < leftArr.length) {
            arr[i] = leftArr[leftIndex];
            leftIndex++;
            i++;
        }

        while (rightIndex < rightArr.length) {
            arr[i] = rightArr[rightIndex];
            rightIndex++;
            i++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {45, 12, 48, 19, 36, 14, 30, 69};

        System.out.println("Mang ban dau: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("Mang da duoc sap xep: " + Arrays.toString(arr));
    }
}

# Hàm sắp xếp
def mergeSort(lst):
    # Cho một cái base case vì đây là hàm đệ quy
    if len(lst) <= 1:
        return
    
    # Tạo hai danh sách phụ để lưu trữ hai mảnh đã bẻ đôi
    mid = len(lst) // 2
    leftLst = lst[:mid]
    rightLst = lst[mid:]

    # Gọi đệ quy để tiếp tục sắp xếp
    mergeSort(leftLst)
    mergeSort(rightLst)

    # Gọi hàm merge để ghép hai mảnh lại với nhau thành danh sách đã được sắp xếp
    merge(lst, leftLst, rightLst)

# Hàm để ghép các mảnh lại với nhau
def merge(lst, leftLst, rightLst):
    leftIndex = 0 # Biến giữ vị trí phần tử được so sánh ở mảnh bên trái
    rightIndex = 0 # Biến giữ vị trí phần tử được so sánh ở mảnh bên phải
    i = 0 # Biến giữ vị trí tiếp theo được ghép vào ở mảng arr

    # Vòng lặp while để so sánh và ghép các phần tử lại với nhau
    while leftIndex < len(leftLst) and rightIndex < len(rightLst):
        # Phần tử nào nhỏ hơn thì ghép vào
        if leftLst[leftIndex] < rightLst[rightIndex]:
            lst[i] = leftLst[leftIndex]
            leftIndex += 1
        else:
            lst[i] = rightLst[rightIndex]
            rightIndex += 1
        i += 1

    # Ghép các phần tử dư thừa vào mảng arr nếu có
    while leftIndex < len(leftLst):
        lst[i] = leftLst[leftIndex]
        leftIndex += 1
        i += 1

    while rightIndex < len(rightLst):
        lst[i] = rightLst[rightIndex]
        rightIndex += 1
        i += 1

lst = [45, 12, 48, 19, 36, 14, 30, 69]

print(f"Danh sách ban đầu: {lst}")
mergeSort(lst)
print(f"Danh sách đã được sắp xếp: {lst}")

// Hàm sắp xếp
function mergeSort(arr) {
    // Cho một cái base case vì đây là hàm đệ quy
    if (arr.length <= 1) {
        return;
    }

    // Tạo hai mảng phụ để lưu trữ hai mảnh đã bẻ đôi
    let mid = Math.floor(arr.length / 2);
    let leftArr = arr.slice(0, mid);
    let rightArr = arr.slice(mid);

    // Gọi đệ quy để tiếp tục sắp xếp
    mergeSort(leftArr);
    mergeSort(rightArr);

    // Gọi hàm merge để ghép hai mảnh lại với nhau thành mảng đã được sắp xếp
    merge(arr, leftArr, rightArr);
}

// Hàm để ghép các mảnh lại với nhau
function merge(arr, leftArr, rightArr) {
    let leftIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên trái
    let rightIndex = 0; // Biến giữ vị trí phần tử được so sánh ở mảnh bên phải
    let i = 0; // Biến giữ vị trí tiếp theo được ghép vào ở mảng arr

    // Vòng lặp while để so sánh và ghép các phần tử lại với nhau
    while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        // Phần tử nào nhỏ hơn thì ghép vào
        if (leftArr[leftIndex] < rightArr[rightIndex]) {
            arr[i] = leftArr[leftIndex];
            leftIndex++;
        } else {
            arr[i] = rightArr[rightIndex];
            rightIndex++;
        }
        i++;
    }

    // Ghép các phần tử dư thừa vào mảng arr nếu có
    while (leftIndex < leftArr.length) {
        arr[i] = leftArr[leftIndex];
        leftIndex++;
        i++;
    }

    while (rightIndex < rightArr.length) {
        arr[i] = rightArr[rightIndex];
        rightIndex++;
        i++;
    }
}

let arr = [45, 12, 48, 19, 36, 14, 30, 69];

window.alert("Mảng ban đầu: " + arr);
mergeSort(arr);
window.alert("Mảng đã được sắp xếp: " + arr);

• Nhanh, có hiệu suất cao với độ phức tạp thời gian ổn định: Như đã phân tích trên, thuật toán sắp xếp trộn có độ phức tạp về thời gian là O(n log n), giúp cho thuật toán trở nên rất nhanh với dữ liệu khổng lồ và thời gian không bị phí.
• Được sử dụng rộng rãi trong các ứng dụng yêu cầu sắp xếp dữ liệu lớn: Vì ưu điểm nói trên mà thuật toán sắp xếp trộn được sử dụng rất rộng rãi để tối ưu thời gian sắp xếp.
• Ổn định: Merge Sort là một thuật toán ổn định, có nghĩa là các phần tử bằng nhau không thay đổi thứ tự sau khi được sắp xếp. Điều này làm cho Merge Sort phù hợp trong các tình huống yêu cầu bảo toàn sự ổn định của dữ liệu.

Hạn chế

• Tốn bộ nhớ: Như đã phân tích trên, thuật toán sắp xếp trộn có độ phức tạp về bộ nhớ O(n), vì thuật toán yêu cầu thêm bộ nhớ trong quá trình sắp xếp. Điều này có thể làm tăng sự sử dụng bộ nhớ và gây lãng phí, đặc biệt là khi xử lý các tập dữ liệu lớn. Việc quản lý bộ nhớ là một yếu tố cần được lưu ý khi triển khai sắp xếp trộn.
• Không phải lúc nào cũng tối ưu hóa được với danh sách gần như đã sắp xếp hoặc đã sắp xếp hoàn toàn: Trong trường hợp dữ liệu đã sắp xếp hoặc gần như đã sắp xếp, thuật toán sắp xếp trộn vẫn phải thực hiện quá trình chia nhỏ và trộn, dẫn đến một số thao tác không cần thiết.

Ứng dụng