Merge Sort
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
Approach
Merge Sort là một thuật toán sắp xếp dạng chia để trị (divide and conquer). Ý tưởng cốt lõi của Merge Sort gồm hai bước lớn: chia nhỏ mảng thành các mảng con cho đến khi mỗi mảng chỉ còn một phần tử, sau đó trộn (merge) các mảng con đã được sắp xếp lại thành một mảng lớn đã sắp xếp
Các bước cụ thể:
Một số lưu ý:
Solution
1export default function recursiveMergeSort(arr: Array<number>): Array<number> {
2 if (arr.length <= 1) return arr;
3 const mid = Math.floor(arr.length / 2);
4 const left = recursiveMergeSort(arr.slice(0, mid));
5 const right = recursiveMergeSort(arr.slice(mid));
6 return merge(left, right);
7}
8
9function merge(left: Array<number>, right: Array<number>): Array<number> {
10 const res = [];
11 let l = 0,
12 r = 0;
13 while (l < left.length && r < right.length) {
14 if (left[l] < right[r]) res.push(left[l++]);
15 else res.push(right[r++]);
16 }
17 res.push(...left.slice(l), ...right.slice(r));
18 return res;
19}