Sorting a partially sorted array [duplicate]

This question al开发者_运维百科ready has answers here: Closed 11 years ago.

Possible Duplicate:

Interview Q: sorting an almost sorted array (elements misplaced by no more than k)

I have a partially sorted array with the property that every element is within d units of its properly sorted position. I am wondering if there is a way to sort this array -- by exploiting this fact -- in less than n log n time.

---

Off the top of my head...

Create a "sliding window" of size 2d.

Start it at [0,2d). Sort the elements in the window; now elements 0 through d-1 are guaranteed to be correct.

Slide the window forward by d, so now it's [d,3d). Sort those elements, guaranteeing that elements d through 2d-1 are correct.

Slide it forward another d, so now its [2d,4d). Sort those. And so on.

Each sort is O(d log d), and it takes n/d steps to get to the end, so this is O(n/d * d log d) = O(n log d). If d is constant, that's O(n).

[edit]

You make a good point in a comment; I did not prove that each iteration preserves the property that every element is within d units of its proper position.

So...

Lemma: If A is an array with the property that every element is within d units of its proper position, and you sort any contiguous subsequence within A to create an array A', then every element in A' is within d units of its proper position.

Proof: Since this is a lemma about the properties of a sort (not performance), it does not matter what algorithm we use to sort. So use bubble sort. Find any two elements in the subsequence that are out of order, and swap them. There are only three cases: Both elements are before their proper positions in the array; both are after their proper positions in the array; or they are between their proper positions in the array.

For example, suppose A[i] belongs at position i' and A[j] belongs at position j', i < j, but A[i] > A[j]. It follows that i' > j' (because that is where the elements "belong", and A[i] > A[j]). Case 1: Suppose i' and j' are both greater than i and j; that is, the order goes i < j < j' < i'. But by hypothesis, i' is only d units from i, so this entire range is only d units wide at most. So j is also within d units of i' and i is within d units of j', so when we swap A[i] with A[j], both elements are still within d of where they belong. The analysis for Case 2 and Case 3 are similar.

So each step of a bubble sort -- on any subsequence of A -- will preserve the desired property, from which it follows that the entire bubble sort will preserve the desired property, from which it follows that any sort will preserve the desired property. Q.E.D.

---

Yes; it is possible to sort in O(nd) time. One solution is a simple modification of insertion sort. We process the input array from start to finish; for each element, we look at the last d elements of the output array, and insert the new element in its appropriate position.

There may, of course, be faster algorithms; this particular choice of algorithm was to make it easier to demonstrate asymptotic bound.

---

Yep. Believe it or not the bubble sort is probably the best for a partially sorted array. It's best case is a fully sorted array in which case its performance is O(n).

Wikipedia on bubble sorts: http://en.wikipedia.org/wiki/Bubble_sort

Edit: Specifically the "Modified Bubble Sort", with a flag to skip exchanges when it is already in order.

---

I believe Timsort (which Python uses I think?) does exactly this.

---

The general idea is to use an adaptive sort. Straight insertion sort is one, timsort is another. These automatically take into account partial sorting.