Ta đã biết tìm kiếm nhị phân trên các dãy đã sắp xếp có độ phức tạp thời gian tốt hơn so với các thuật toán tìm kiếm trên dãy chưa sắp xếp. Chính vì thế, việc sắp xếp thông tin theo một trình tự nào đó luôn đóng vai trò quan trọng trong các bài toán tìm kiếm thông tin. Tuy nhiên, một số thuật toán sắp xếp mà em đã biết như sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt, ... đều có độ phức tạp thời gian O (n2) (n - kích thước dãy cần sắp xếp). Câu hỏi đặt ra là: Liệu có hay không một cách sắp xếp dãy với thời gian tốt hơn O (n2)?

Liệu kĩ thuật chia để trị có thể áp dụng cho bài toán sắp xếp được không? Nếu có thì có làm tăng hiệu quả của sắp xếp được không?