Bài toán
Cho T[1..n] là một mảng n phần tử. Vấn đề đặt ra là sắp xếp các phần tử này theo thứ tự tăng. Chúng ta đã có thể giải quyết vấn đề này bằng các phương pháp selection sort hay insertion sort hoặc là heapsort
Như chúng ta đã biết thời gian dùng selection sort hay insertion sort để sắp xếp mảng T trong cả hai trường hợp: xấu nhất và trung bình đều vào cỡ n2. Còn heapsort vào khoảng nlogn.
Có một số giải thuật đặc biệt cho bài toán này theo mô hình chia để trị đó là mergesort và quicksort, chúng ta sẽ lần lượt đi nghiên cứu chúng.
MergeSort
Chia để trị tiếp cận tới bài toán này bằng việc tách mảng T thành hai phần mà kích thước của chúng sai khác nhau càng ít càng tốt, sắp xếp các phần này bằng cách gọi đệ qui và sau đó trộn chúng lại (chú ý duy trì tính thứ tự). Để làm được điều này chúng ta cần một giải thuật hiệu quả cho việc trộn hai mảng đã được sắp U và V thành một mảng mới T mà kích thước của mảng T bằng tổng kích thước của hai mảng U và V. Vấn đề này có thể thực hiện tốt hơn nếu ta thêm vào các ô nhớ có sẵn ở cuối của mảng U và V các giá trị cầm canh (giá trị lớn hơn tất cả các giá trị trong U và V, giả sử là )
Hình sau chỉ ra các bước của mergesort.
Mảng đã được sắp theo thứ thự tăng
Giải thuật sắp xếp này minh hoạ tất cả các khía cạnh của chia để trị. Khi số lượng các phần tử cần sắp là nhỏ thì ta thường sử dụng các giải thuật sắp xếp đơn giản.
Khi số phần tử đủ lớn thì ta chia mảng ra 2 phần, tiếp đến trị từng phần một và cuối cùng là kết hợp các lời giải.
* Độ phức tạp thuật toán:
Bài toán chia thành các bước
Với mỗi lần merge thứ i, độ phức tạp bài toán là O(n)
Số lần merge là O(log n)
Thời gian tổng cộng: O(n logn)
Như vậy hiệu quả của mergesort tương tự heapsort. Trong thực tế sắp xếp trộn có thể nhanh hơn heapsort một ít nhưng nó cần nhiều hơn bộ nhớ cho các mảng trung gian U và V. Ta nhớ lại heapsort có thể sắp xếp tại chỗ (in-place), và cảm giác nó chỉ sử dụng một ít biến phụ mà thôi. Theo lý thuyết mergesort cũng có thể làm được như vậy tuy nhiên giá thành có tăng một chút ít.
Quicksort
Giải thuật này được phát minh bởi Hoare, nó thường được hiểu như là tên gọi của nó - sắp xếp nhanh, hơn nữa nó cũng dựa theo nguyên tắc chia để trị. Không giống như mergesort nó quan tâm đến việc giải các bài toán con hơn là sự kết hợp giữa các lời giải của chúng. Bước đầu tiên của giải thuật này là chọn 1 vật trung tâm (pivot) từ các phần tử của mảng cần sắp. Tiếp đến vật trung tâm sẽ ngăn mảng này ra 2 phần: các phần tử lớn hơn vật trung tâm thì được chuyển về bên phải nó, ngược lại thì chuyển về bên trái. Sau đó mỗi phần của mảng được sắp xếp độc lập bằng cách gọi đệ qui giải thuật này. Cuối cùng mảng sẽ được sắp xếp xong. Để cân bằng kích thước của 2 mảng này ta có thể sử dụng phần tử ở giữa (median) như là vật trung tâm . Đáng tiếc là việc tìm phần ở giữa cũng mất 1 thời gian đáng kể. Để giải quyêt điều đó đơn giản là chúng ta sử dụng 1 phần tử tuỳ ý trong mảng cần sắp như là vật trung tâm và hi vọng nó là tốt nhất có thể.
Việc thiết kế giải thuật ngăn cách mảng bằng vật trung tâm với thời gian tuyến tính không phải là sự thách đố (có thể làm được). Tuy nhiên điều đó là cần thiết để so sánh với các giải thuật sắp xếp khác như là heapsort. Vấn đề đặt ra là mảng con T[i..j] cần được ngăn bởi vật trung tâm p=T[i]. Một cách làm có thể chấp nhận được là: Duyệt qua từng phần tử của của nó chỉ một lần nhưng bắt đầu từ hai phía (đầu và cuối mảng). Khi đó khởi tạo k=i; l=j+1, k tăng dần cho đến khi T[k] > p, l giảm dần cho đến khi T[l] ( l. Tiếp đến hoán vị T[k] và T[l]. Quá trình này tiếp tục cho đến khi k ( l. Cuối cùng đổi chổ T[i] và T[l] cho nhau và lúc này ta xác định đúng vị trí của phần tử trung tâm.
* Mô tả thuật toán:
quicksort(L)
{
if (length(L) < 2) return L
else
{
pick some x in L // x là phần tử chốt
L1 = { y in L : y < x }
L2 = { y in L : y > x }
L3 = { y in L : y = x }
quicksort(L1)
quicksort(L2)
return concatenation of L1, L3, and L2
}
}
Hình vẽ sau cho thấy sự làm việc của pivot và quicksort.
Hình 4.2
Quicksort sẽ không hiệu quả nếu sử dụng việc gọi đệ quy của các bài toán con mà không chú ý đến sự cân bằng kích thước của chúng. Tình huống xấu nhất là khi T đã được sắp trước mà gọi quicksort và thời gian dùng quicksort để sắp là ((n2).
Gọi t(n) là thời gian trung bình dùng quicksort để sắp mảng n phần tử T[1..n]. l là giá trị trả về khi gọi pivot(T[1..n],l). Theo pivot() thì l nằm giữa 1 ( n và xác suất là 1/n. Thời gian để tìm vật trung tâm g(n) là tuyến tính. Thời gian để dùng đệ qui để sắp xếp hai mảng con kích thước (l-1) và (n-l) tương ứng là t(n-1) và t(n-l). Như vậy với n đủ lớn ta có:
Hay rõ ràng hơn ta chọn n0 là giá trị đủ lớn để sử dụng công thức trên. Nghĩa là nếu n < n0 thì ta dùng sắp xếp chèn. Khi đó gọi d là hằng số sao cho g(n) ≤ dn với n>n0.
Với công thức kiểu như 2.4 quả là khó phân tích độ phức tạp. Ta dự đoán nó tương tự mergesort và hi vọng nó là như vậy tức là vào cỡ O(nlogn).
Thật vậy ta có định lý sau:
Định lý: Quicksort cần nlogn thời gian để sắp xếp n phần tử trong trường hợp trung bình.
Chứng minh
Gọi t(n) là thời gian cần thiết để sắp n phần tử trong trường hợp trung bình.
a, n0 là các hằng số giống như công thức 2.4
Ta chứng minh t(n) = cnlogn với mọi n ≥ 2. với c là hằng số.
Dùng phương pháp qui nạp để c/m:
- Với mọi n nguyên dương: (2 ≤ n ≤ n0) 
- Bước qui nạp
Giả thiết rằng: t(k) ≤ cklogk với mọi 2≤ k < n
ta chỉ ra c sao cho t(n) ≤ cnlogn
Lấy a = t(0) +t(1)
Từ 7.2 ta có
Theo giả thiết qui nạp : t(k) = cklogk
Từ đó chúng ta chỉ xem xét với những n > n0 thoả mãn:
Kết hợp cả 2 điều kiện trong (2.5) và (2.6) ta có
Hay ta có t(n) ≤ cnlogn với mọi n ≥ 2, và như vậy định lý được chứng minh.
Như vậy quicksort có thể sắp xếp 1 mảng n phần tử khác nhau trong trường hợp trung bình là O(nlogn). Câu hỏi đặt ra là liệu có thể sửa đổi quicksort để nó sắp xếp với thời gian O(nlogn) trong trương hợp xấu nhất hay không. Câu trả lời là có thể!!!. Tuy nhiên nếu việc tìm phần tử ở giữa của T[i..j] là tuyến tính và lấy nó làm vật trung tâm (pivot) (Finding the median) thì quicksort cũng cần O(n2) để sắp xếp n phần tử trong trường hợp xấu nhất (khi tất cả các phần tử của mảng cần sắp là bằng nhau).