Merge Sort (Sắp xếp trộn)
Thuật toán chia để trị (divide-and-conquer). Chia mảng thành các mảng con đơn lẻ, sau đó trộn (merge) cặp mảng con đã sắp xếp.
Các bước
- Chia mảng liên tục cho đến khi mỗi mảng con chỉ còn 1 phần tử.
- So sánh và trộn 2 mảng con thành mảng đã sắp xếp.
- Lặp lại cho đến khi còn 1 mảng duy nhất.
Ví dụ code
<html> <body> <script> function mSort(array) { if (array.length === 1) { return array; } const middle = Math.floor(array.length / 2); const left = array.slice(0, middle); const right = array.slice(middle); return merge(mSort(left), mSort(right)); } function merge(left, right) { let result = []; let leftIndex = 0; let rightIndex = 0; while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] < right[rightIndex]) { result.push(left[leftIndex]); leftIndex++; } else { result.push(right[rightIndex]); rightIndex++; } } return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex)); } const list = [4,7,5,9,1,3,8,2]; document.write("Kết quả: " + mSort(list)); </script> </body> </html>
Kết quả
1,2,3,4,5,7,8,9