Kim & Kutzner tamc2008 paper: analysis in the case of a lot of identical key elements for sorting
nsajko opened this issue · 0 comments
nsajko commented
Please take a look at Theorem 1 in the paper. It proves that the merge takes O(n) assignments, but the reasoning for the case where the rotation based variant of Hwang&Lin should be used for local merges is left to the reader to prove in the end, with a pointer to Lemma 3. To be honest, it seems to me that the proof does not even work for that case, that is that the merge is O(n * sqrt(n)) in that case instead of O(n).
Links to paper: https://pdfs.semanticscholar.org/9533/29f19587e24b0969b7e0b55d5e92f3dcab2a.pdf
http://itbe.hanyang.ac.kr/ak/papers/tamc2008.pdf