Không thể thực hiện được, mặc dù công việc của tôi sẽ dễ dàng hơn nhiều nếu nó là :).
Bạn có yếu tố O (log n) mà bạn không thể tránh. Bạn có thể chọn để lấy nó như là thời gian hoặc không gian, nhưng cách duy nhất để tránh nó là không sắp xếp. Với không gian O (log n), bạn có thể xây dựng danh sách các lần tiếp tục theo dõi vị trí bạn đã lưu trữ các phần tử không hoàn toàn phù hợp. Với đệ quy này có thể được thực hiện để phù hợp với O (1) đống, nhưng đó là chỉ bằng cách sử dụng O (log n) stack khung thay thế.
Đây là tiến độ của tỷ lệ phân loại hợp nhất và phát triển từ 1-9.Lưu ý cách bạn yêu cầu tính toán không gian log để theo dõi các đảo ngược thứ tự do các ràng buộc song song của không gian cố định và các hoán đổi tuyến tính.
. -
135792468
. -
135792468
: .-
125793468
: .-
123795468
#.:-
123495768
:.-
123459768
.:-
123456798
.-
123456789
123456789
Có một số điều kiện biên tinh tế, một chút khó khăn hơn so với tìm kiếm nhị phân để có được quyền, và ngay cả trong này hình thức (có thể), và do đó là một vấn đề bài tập về nhà xấu; nhưng một bài tập tâm thần thực sự tốt.
Cập nhật Dường như tôi nhầm lẫn và có một thuật toán cung cấp thời gian O (n) và O (1). Tôi đã tải xuống các giấy tờ để soi sáng bản thân mình và rút câu trả lời này là không chính xác.
Câu hỏi có nêu rõ loại hợp nhất không? Tôi biết nó có thể hợp nhất sắp xếp tại chỗ, nhưng không phải trong thời gian O (n) (ít nhất tôi chưa bao giờ nghe nói về nó.) – jrista
Không, nó không. Tôi đang làm tương tự với bước hợp nhất. Nó trông tương tự. – Sid
Nếu bạn đã đăng chính xác từ ngữ của câu hỏi, thì có vẻ như không liên quan gì đến việc hợp nhất. Có các thuật toán sắp xếp là không gian O (1) và O (n) tại chỗ cho một mảng được sắp xếp trước (tức là sắp xếp chèn). Mergesort không phải là một trong số họ, và nó nổi tiếng rằng nó không phải là một trong số họ, vì vậy ... – jrista