Merge sort with divide and conquer: suppose n by n array,
Method 1. 1-> Get sorted top half and sorted bottom half, (To get sorted top half and sorted bottom half, recursively using this process) 2-> and merge them together. Time complexity: T(n * n) = 2 * T(n/2 * n) + n * n [until only 2 rows left] ==> T(n * n) = n * n * log2 n do not use property " column is sorted " Method 2. 1-> Divide the square into 4 sub area, top-left(A), top-right(B), bottom-left(C), bottom-right(D) 2-> Get every area sorted (recursively) 3-> Connect A and D directly, every cell in D is bigger than every cell in A (call the new sorted array A-D) 4-> Merge B and C, call it B-C 5-> Merge A-D and B-C Time complexity: T(n * n) = 4 * T(n/2 * n/2) + 1.5 * n * n [until only 2 rows left] ==> T(n * n) = 1.5 * n * n * log4 n (a bit faster than method 1) On Feb 7, 4:43 pm, jalaj jaiswal <[email protected]> wrote: > You are given a array with rows sorted and column sorted. You have to print > entire array in sorted order. > > -- > With Regards, > *Jalaj Jaiswal* (+919019947895) > Software developer, Cisco Systems > Final Year Undergraduate, > IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
