Thư viện chuẩn dùng thuật toán sắp xếp nào, và vì sao không phải quicksort thuần?

Chi tiết đáng nói là TÍNH ỔN ĐỊNH, vì nó quyết định đúng/sai chứ không chỉ tốc độ. Sắp xếp ổn định giữ nguyên thứ tự tương đối của các phần tử bằng nhau, nên bạn sắp theo tên rồi sắp theo phòng ban và vẫn còn thứ tự tên trong mỗi phòng ban. Java dùng Timsort (ổn định) cho object và quicksort (không ổn định) cho kiểu nguyên thuỷ — vì với int thì hai giá trị bằng nhau không phân biệt được, nên tính ổn định vô nghĩa.

Timsort thắng vì dữ liệu thật hiếm khi ngẫu nhiên: log đã gần đúng thứ tự thời gian, danh sách người dùng đã gần đúng theo id. Nó tìm các đoạn tăng hoặc giảm sẵn có rồi trộn chúng, nên với dữ liệu đã sắp thì chi phí là O(n) chứ không phải O(n log n). Đó là một tối ưu hoá cho phân phối đầu vào thực tế, không phải cho trường hợp lý thuyết.

Điều thực tế nhất: gần như bạn không nên tự viết sắp xếp. Chỗ đáng để ý là HÀM SO SÁNH — một comparator không nhất quán (a < b và b < a cùng đúng) làm Timsort ném IllegalArgumentException trong Java, và cho kết quả không xác định ở nơi khác. Và trong JavaScript, [10, 9, 1].sort() trả về [1, 10, 9] vì mặc định so sánh theo chuỗi.