Rumah  >  Artikel  >  hujung hadapan web  >  Merge Sort Demystified: Panduan Pemula untuk Memecahkan dan Menakluk Isih

Merge Sort Demystified: Panduan Pemula untuk Memecahkan dan Menakluk Isih

DDD
DDDasal
2024-09-12 20:17:21331semak imbas

Merge Sort Demystified: A Beginner

Merge Sort was introduced by John von Neumann in 1945, primarily to improve the efficiency of sorting large datasets. Von Neumann's algorithm aimed to provide a consistent and predictable sorting process using the divide and conquer method. This strategy allows Merge Sort to handle both small and large datasets effectively, guaranteeing a stable sort with a time complexity of O(n log n) in all cases.

Merge Sort employs the divide and conquer approach, which splits the array into smaller subarrays, recursively sorts them, and then merges the sorted arrays back together. This approach breaks the problem into manageable chunks, sorting each chunk individually and combining them efficiently. As a result, the algorithm performs well even on large datasets by dividing the sorting workload.

Recursion is a process where a function calls itself to solve a smaller version of the same problem. It keeps breaking the problem down until it reaches a point where the problem is simple enough to solve directly, which is called the base case.

Below is an implementation of Merge Sort in JavaScript, showing how the array is recursively split and merged:

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

To better understand how Merge Sort works, let's walk through the process using the array: [38, 27, 43, 3, 9, 82, 10]

Step 1: Recursive Division (mergeSort function)
The array is recursively split into smaller subarrays until each subarray has only one element. This happens through the following lines in the mergeSort function:

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

That stops our recursion.

Here’s how the recursive division unfolds:

  • Initial Call: mergeSort([38, 27, 43, 3, 9, 82, 10])
    • The array is split at the midpoint: [38, 27, 43] and [3, 9, 82, 10]
  • First Half:

    • mergeSort([38, 27, 43])
      • Split at the midpoint: [38] and [27, 43]
    • mergeSort([27, 43])
      • Split into [27] and [43]
    • Subarrays [38], [27], and [43] are now individual elements and ready to be merged.
  • Second Half:

    • mergeSort([3, 9, 82, 10])
      • Split at the midpoint: [3, 9] and [82, 10]
    • mergeSort([3, 9])
      • Split into [3] and [9]
    • mergeSort([82, 10])
      • Split into [82] and [10]
    • Subarrays [3], [9], [82], and [10] are now ready to be merged.

Step 2: Merging the Sorted Subarrays (merge function)
Now, we start merging the subarrays back together in sorted order using the merge function:

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

Here’s how the merging process works:

First Merge (from the base cases):

  • Merge [27] and [43] → Result is [27, 43]
  • Merge [38] with [27, 43] → Result is [27, 38, 43]

At this point, the left half of the array is fully merged: [27, 38, 43].

Second Merge (from the base cases):

  • Merge [3] and [9] → Result is [3, 9]
  • Merge [82] and [10] → Result is [10, 82]
  • Merge [3, 9] with [10, 82] → Result is [3, 9, 10, 82]

Now, the right half is fully merged: [3, 9, 10, 82].

Step 3: Final Merge
Finally, the two halves [27, 38, 43] and [3, 9, 10, 82] are merged using the merge function:

Compare 27 (left[0]) and 3 (right[0]). Since 3 < 27, add 3 to the result.
Compare 27 and 9. Add 9 to the result.
Compare 27 and 10. Add 10 to the result.
Compare 27 and 82. Add 27 to the result.
Compare 38 and 82. Add 38 to the result.
Compare 43 and 82. Add 43 to the result.
Add the remaining element 82 from the right array.
The fully merged and sorted array is:
[3, 9, 10, 27, 38, 43, 82].

Time Complexity: Best, Average, and Worst Case: O(n log n)
Let's look at it closer:

Dividing (O(log n)): Each time the array is split into two halves, the size of the problem is reduced. Since the array is divided in half at each step, the number of times you can do this is proportional to log n. For example, if you have 8 elements, you can divide them in half 3 times (since log₂(8) = 3).

Merging (O(n)): After dividing the array, the algorithm merges the smaller arrays back together in order. Merging two sorted arrays of size n takes O(n) time because you have to compare and combine each element once.

Kerumitan Keseluruhan (O(n log n)): Memandangkan pembahagian mengambil langkah O(log n) dan anda menggabungkan n elemen pada setiap langkah, jumlah kerumitan masa ialah pendaraban kedua-dua ini: O(n log n).

Kerumitan Angkasa: O(n)
Isih Gabung memerlukan ruang tambahan yang berkadar dengan saiz tatasusunan kerana ia memerlukan tatasusunan sementara untuk menyimpan elemen semasa fasa cantuman.

Perbandingan dengan Algoritma Isih Lain:
QuickSort: Walaupun QuickSort mempunyai purata kerumitan masa O(n log n), kes terburuknya boleh menjadi O(n^2). Merge Sort mengelakkan senario terburuk ini, tetapi QuickSort biasanya lebih pantas untuk pengisihan dalam memori apabila ruang menjadi kebimbangan.
Isih Buih: Jauh kurang cekap daripada Isih Gabung, dengan kerumitan masa O(n^2) untuk senario purata dan terburuk.

Penggunaan Dunia Sebenar
Merge Sort digunakan secara meluas untuk pengisihan luaran, di mana set data yang besar perlu diisih daripada cakera, kerana ia mengendalikan data yang tidak sesuai dengan memori dengan cekap. Ia juga lazimnya dilaksanakan dalam persekitaran pengkomputeran selari, di mana subarray boleh diisih secara bebas, mengambil kesempatan daripada pemprosesan berbilang teras.

Selain itu, perpustakaan dan bahasa seperti Python (Timsort), Java dan C++ (std::stable_sort) bergantung pada variasi Merge Sort untuk memastikan kestabilan dalam operasi pengisihan, menjadikannya sangat sesuai untuk menyusun objek dan struktur data yang kompleks.

Kesimpulan
Merge Sort terus menjadi algoritma asas dalam kedua-dua sains komputer teori dan aplikasi praktikal kerana kestabilan, prestasi konsisten dan kebolehsuaiannya untuk mengisih set data yang besar. Walaupun algoritma lain seperti QuickSort mungkin berprestasi lebih pantas dalam situasi tertentu, Merge Sort dijamin O(n log n) kerumitan masa dan serba boleh menjadikannya tidak ternilai untuk persekitaran yang dikekang memori dan untuk mengekalkan susunan elemen dengan kunci yang sama. Peranannya dalam perpustakaan pengaturcaraan moden memastikan ia kekal relevan dalam aplikasi dunia sebenar.

Sumber:

  1. Knuth, Donald E. The Art of Computer Programming, Vol. 3: Menyusun dan Mencari. Addison-Wesley Professional, 1997, hlm. 158-160.
  2. Cormen, Thomas H., et al. Pengenalan kepada Algoritma. MIT Press, 2009, Bab 2 (Isih Gabung), Bab 5 (Kerumitan Algoritma), Bab 7 (Isih Pantas).
  3. Silberschatz, Abraham, et al. Konsep Sistem Pangkalan Data. McGraw-Hill, 2010, Bab 13 (Isih Luaran).
  4. "Timsort." Dokumentasi Python, Yayasan Perisian Python. Python's Timsort
  5. "Java Arrays.sort." Dokumentasi Oracle. Java's Arrays.sort()

Atas ialah kandungan terperinci Merge Sort Demystified: Panduan Pemula untuk Memecahkan dan Menakluk Isih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn