Homework 5 Incorrect sorting algorithm

1. Prove that the incorrect sorting algorithm below runs in O(n lg n) time.
(Hint: you may use the fact that Pn
i=1
1
i = O(lg n).)
Input: data: an array of integers to sort
Input: n: the number of values in data
Output: a permutation of data such that
data[1] ≤ data[2] ≤ . . . ≤ data[n]
1 Algorithm: BadSort
2 foreach i = n − 1 to 1 step −1 do
3 foreach j = 1 to n − i step i do
4 if data[j] data[j + i] then
5 Swap data[j] and data[j + i]
6 end
7 end
8 end
9 return data
1