Can't we use bubble sort on remaining elements?
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements are
already sorted
(though we know nothing about the remaining elements). Give an
algorithm that
sorts A in
merge sort or quick sort or insert last root(n) element . This will take max
n time . now merge the last root(n) element with the starting element .this
will take n time . so final time complexity is nnlog(n)
Rahul
--
You received this message because you are subscribed to the Google
ooops wrong approach... :(
On Thu, Aug 26, 2010 at 10:44 PM, Naveen Kumar
naveenkumarve...@gmail.comwrote:
Can't we use bubble sort on remaining elements?
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements are
Hi Sourav,
I will first inplace sort the last √n elements in O(n) and then merge the
two sorted arrays in O(n).
The only problem: O(n) merging will not be inplace.
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements
