Best sorting algorithm for a partly sorted sequence?

Question

I have to answer the following question:

What sorting algorithm is recommended if the first n-m part
is already sorted and the remaining part m is unsorted? Are there any algorithms that take O(n log m) comparisons? What about O(m log n) comparisons?

I just can't find the solution.

My first idea was insertion sort because O(n) for almost sorted sequence. But since we don't know the size of m the Runtime is very likely to be O(n^2) eventough the sequence is half sorted already isn't it?

Then I tought perhabs its quick sort because it takes (Sum from k=1 to n) Cavg (1-m) + Cavg (n-m) comparisons. But after ignoring the n-m part of the sequence the remaining sequence is 1-m in quicksort and not m.

Merge Sort and heap sort should have a runtime of O(m log m) for the remaining sequence m I would say.

Does anyone have an idea or can give me some advice?

Greetings

Because this is a pure algorithmic question, it may better suit [cs.se] (but remember to read their help center before asking) / Besides, it's impossible to get less than the time for reading the sequence which is already O(n). — user202729, May 14 '18 at 08:11
If you know which part is sorted, sort only the rest and than merge the two sorted parts. — MrSmith42, May 14 '18 at 08:24

Sasha · Accepted Answer · 2018-05-14T08:17:17.270

2

Have you tried sorting remaining part m separately as O(m log (m)) complexity (with any algorithm you like: MergeSort, HeapSort, QuickSort, ...) and then merge that part with sorted part using MergeSort (You won't even need to fully implement MergeSort - just single pass of it's inner loop body to merge two sorted sequences)?

That would result in O(m*log(m) + n + m) = O(m*log(m) + n) complexity. I don't believe it is possible to find better asymptotic complexity on single-core CPU. Although it will require additional O(n+m) memory for merging result array.

edited May 14 '18 at 08:17

answered May 14 '18 at 08:12

Sasha

8,537
4
49
76

Remark: *QuickSort* is in worst case **O(n²)** not O(n log n). – MrSmith42 May 14 '18 at 08:22
Thanks for the help :) – Dennis May 14 '18 at 10:36
Use binary search instead of linear scan to find the merge positions of the final **m** items. Then number of comparisons is **O(m log mn)** – Matt Timmermans May 14 '18 at 17:52
@MattTimmermans, How should binary search help? You still need to insert those elements somehow. And inserting in the middle of array will require shifting all remaining items. – Sasha May 14 '18 at 19:28
Yes. I expect that's why the OP specifically asked about the number of comparisons – Matt Timmermans May 14 '18 at 20:49

score 0 · Answer 2 · answered May 14 '18 at 08:11

0

Which sort algorithm works best on mostly sorted data?

Sounds like insertion and bubble are good. You are free to implement as many as you want then test to see which is faster/fewer operations by supplying them partially sorted data.

answered May 14 '18 at 08:11

Shefeto

178
1
10

Best sorting algorithm for a partly sorted sequence?

2 Answers2