Sortir array dari

Saya mencoba memahami bagaimana saya bisa mengurutkan array $n$ elemen saat saja $\log n$ tidak ada di tempat.

Saya mendengar bahwa paling banyak menyortir array $I$ inversi memiliki kompleksitas $O(n\log(I/n))$. Karena ada$\log n$ elemen yang tidak disortir, dalam kasus saya paling banyak ada $n\log n$ inversi.

Jawaban untuk pertanyaan itu adalah $O(n\log\log n)$ yang konsisten dengan rumus, tetapi saya tidak dapat memahami "ide di baliknya, atau algoritma penyortiran mana yang mencapainya.

Berasumsi bahwa "$k$ elemen tidak pada tempatnya "berarti ada $k$ elemen yang penghapusan meninggalkan sisa array diurutkan, ada $O(n+k\log k)$Algoritma -waktu untuk mengurutkan seluruh array.

Singkatnya, hitung paling tidak panjang selanjutnya $n-2k$, urutkan yang lain, dan gabungkan. Yang pertama dapat dicapai dalam waktu$O(n)$oleh algoritma tumpukan sederhana yang mendorong elemen satu per satu dan muncul dua teratas setiap kali mereka rusak. Strategi penghapusan yang optimal harus menghapus setidaknya satu dari elemen-elemen ini, sehingga total kerusakan dapat dipecahkan oleh$2k$ penghapusan.

Katakanlah ada $k$ elemen bukan tempat.

Membagi array menjadi sub-array yang tidak berkurang. Ini bisa dilakukan di$\Theta(n)$ waktu dan akan menghasilkan paling banyak $2k$subarrays. Sekarang kita hanya menggabungkan keduanya secara berpasangan$\Theta(n \log k)$ waktu, menghasilkan array yang diurutkan.