tôi thấy một bài thuyết trình ngày khác, trong đó loa đã sử dụng các kỹ thuật nêu trong giấy McIlroy của A Killer Adversary for Quicksort để tạo ra một đầu vào để Arrays.sort cho kiểu primitive mà sẽ kích hoạt O (n) hành vi. Trình tự gây ra sự lựa chọn trục xoay luôn luôn chỉ làm giảm kích thước mảng bằng một hằng số, khiến cho hàm Java Arrays.sort gây ra tràn ngăn xếp.Tại sao việc thực hiện JDK của quicksort có nguy cơ tràn ngăn xếp?
Theo the source files from the JDK, chức năng triển khai quicksort Arrays.sort1 không có biện pháp bảo vệ để ngăn chặn tràn ngăn xếp. Nó luôn luôn có thể làm cho quicksort không bao giờ bị tràn do có thói quen sắp xếp không kích hoạt hai cuộc gọi đệ quy, nhưng thay vào đó sử dụng một vòng lặp while để tái sử dụng khung stack hiện tại cho subarray lớn hơn và chỉ đệ quy một lần (trên subarray nhỏ hơn). Điều này gây ra sự suy giảm hiệu suất tối thiểu và làm cho nó không thể gây ra tràn ngăn xếp cho bất kỳ đầu vào có kích thước hợp lý nào, vì chiều sâu ngăn xếp không bao giờ vượt quá khung ngăn xếp O (log n) trên đầu vào có kích thước n. Các tác giả cũng có thể đã sử dụng thuật toán introsort, thuật toán sửa đổi quicksort để chuyển sang thuật toán phân loại O (n log n) tồi tệ nhất khi độ sâu đệ quy quicksort vượt quá giới hạn, để ngăn chặn điều này.
Có lý do nào khiến các tác giả của Arrays.sort không chọn làm điều này? Nó có vẻ như một vấn đề nghiêm trọng mà thuật toán phân loại dựng sẵn có thể gây ra tràn ngăn xếp, vì nó làm cho nó có thể khởi động một cuộc tấn công DoS chống lại một hệ thống như vậy bằng cách kích hoạt các luồng tràn lặp đi lặp lại.
Để biết chắc chắn chúng tôi cần hỏi Vladimir Yaroslavskiy, Jon Bentley hoặc Josh Bloch. Tuy nhiên trong java 1.7, phương thức sort1 được loại bỏ và thay thế bằng một DualPivotQuicksort nhưng tôi không đủ tốt ở công cụ này để hiểu xem điều này có tốt hơn như cách tiếp cận cũ hay không. – mszalbach