Đây là thuật toán sắp xếp đệ quy (recursive) và chia để trị (divide-and-conquer). Bước đầu tiên của thuật toán là chia mảng cần sắp xếp thành các mảng con có kích thước nhỏ hơn, sau đó sắp xếp các mảng con này. Tiếp theo, ta ghép các mảng con lại với nhau để tạo thành một mảng đã sắp xếp.
Thuật toán Merge Sort bao gồm các bước sau:
- Chia mảng cần sắp xếp thành hai mảng con bằng cách tìm phần tử giữa của mảng.
- Đệ quy sắp xếp hai mảng con.
- Ghép hai mảng con đã sắp xếp lại với nhau để tạo thành một mảng đã sắp xếp.
Ví dụ về thuật toán Merge Sort trong Java:
public class MergeSort {
public 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);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left; i <= right; i++) {
arr[i] = temp[i - left];
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 6, 9, 1, 3, 8, 7, 4};
mergeSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}