如何设计O(n)时间复杂度的部分有序数组排序算法？

Alright, let's work through this problem together—you need to fully sort an array where the first chunk is already sorted, and the rest are messy, all while sticking to O(n) time. Here's how to pull it off without writing a single line of code:

First, let's get clear on the numbers to avoid confusion:

• Let N = total elements in your array
• Let M = N - floor(N / sqrt(N)) = length of the pre-sorted prefix
• Let K = floor(N / sqrt(N)) = length of the unsorted suffix (so M + K = N)

The Key Trick #

Here's the critical insight: K is roughly sqrt(N), which means any operation that takes O(K log K) time is asymptotically way smaller than linear time (since sqrt(N) * log sqrt(N) grows far slower than N). That's our loophole—we can safely sort the messy suffix first, then merge it with the sorted prefix in linear time, keeping the total complexity at O(N).

Step-by-Step Breakdown #

• Isolate the unsorted suffix: Grab the last K elements (the disordered ones) and set them aside in a temporary group.
• Sort the temporary group: Use any standard comparison sort (quicksort, mergesort, heapsort—pick your favorite) on this small group. Since K is sqrt(N)-sized, this step takes O(K log K) time, which is well under our O(N) budget.
• Merge the two sorted groups: Now you have two sorted lists: the original prefix and your newly sorted suffix. Perform a classic linear-time merge (like the merge step in mergesort):
  1. Use three pointers to track your position in the prefix, the sorted suffix, and the final array (you can overwrite the original array to save space).
  2. Compare the current elements from each sorted list, place the smaller one into the final array, and move the corresponding pointer forward.
  3. When one list runs out, copy the remaining elements from the other list directly into the final array.

Why This Hits O(N) Time #

• Sorting the suffix: O(K log K) translates to O(sqrt(N) log N), which is asymptotically smaller than O(N)—it's negligible in the big picture.
• Merging the two sorted lists: This takes O(M + K) = O(N) time since together they make up the entire array.
• Adding those two steps gives us O(N + o(N)) = O(N) total time, which meets your requirement perfectly.

Quick Note on In-Place Alternatives #

If you want to avoid using extra space for the temporary group, skip trying to insert each unsorted element into the prefix directly—shifting elements to make space would take O(M) time per insertion, leading to O(K*M) = O(N*sqrt(N)) time, which is way too slow. The merge-based approach is the best bet for sticking strictly to O(N) time.

内容的提问来源于stack exchange，提问作者Br333