algorithm - Sorting a partially sorted array -

possible duplicate:
interview q: sorting sorted array (elements misplaced no more k)

i have partially sorted array property every element within d units of sorted position. wondering if there way sort array -- exploiting fact -- in less n log n time.

off top of head...

create "sliding window" of size 2d.

start @ [0,2d). sort elements in window; elements 0 through d-1 guaranteed correct.

slide window forward d, it's [d,3d). sort elements, guaranteeing elements d through 2d-1 correct.

slide forward d, [2d,4d). sort those. , on.

each sort o(d log d), , takes n/d steps end, o(n/d * d log d) = o(n log d). if d constant, that's o(n).

[edit]

you make point in comment; did not prove each iteration preserves property every element within d units of proper position.

so...

lemma: if array property every element within d units of proper position, , sort contiguous subsequence within create array a', every element in a' within d units of proper position.

proof: since lemma properties of sort (not performance), not matter algorithm use sort. use bubble sort. find 2 elements in subsequence out of order, , swap them. there 3 cases: both elements before proper positions in array; both after proper positions in array; or between proper positions in array.

for example, suppose a[i] belongs @ position i' , a[j] belongs @ position j', < j, a[i] > a[j]. follows i' > j' (because elements "belong", , a[i] > a[j]). case 1: suppose i' , j' both greater , j; is, order goes < j < j' < i'. hypothesis, i' d units i, entire range d units wide @ most. j within d units of i' , within d units of j', when swap a[i] a[j], both elements still within d of belong. analysis case 2 , case 3 similar.

so each step of bubble sort -- on subsequence of -- preserve desired property, follows entire bubble sort preserve desired property, follows any sort preserve desired property. q.e.d.