là một trong những thuật toán có độ phức tạp ở mức trung bình và cùng sử dụng phương pháp chia để trị giống thuật toán sắp xếp nhanh Quicksort rồi gọi đệ quy chính nó trên các phân vùng đã chia. Thuật toán này không chỉ áp dụng trong sắp xếp mà còn ở nhiều bài toán khác. Sự khác biệt chính là Quicksort là thuật toán sắp xếp nội [internal], tại chỗ [in-place] trong khi đó Merge Sort lại là thuật toán sắp xếp ngoại [external], không tại chỗ [not-in-place].
Cài đặt
Thuật toán này chia mảng cần sắp xếp thành 2 nửa. Với phương thức mergeSort[], tiếp tục lặp lại việc này ở các nửa mảng đã chia cho đến khi chỉ còn 1 phần tử. Sau cùng gộp lại thành mảng đã sắp xếp. Phương thức merge[] là tiến trình quan trọng nhất, được sử dụng để gộp hai nửa mảng thành 1 mảng duy nhất đã được sắp xếp.
Khởi đầu với phương thức mergeSort[]:
public static void mergeSort[int[] array, int low, int high] { if [high