We have designed an new algorithm to sort a list of n numbers. We recursively partition the numbers into groups of size sqrt(n) each until we are left with lists of constant size; at which point we use insertion sort to sort the numbers. To combine solutions, we do a merge of the sorted lists, namely maintaining pointers to the start of the list and at each step advancing the pointer of the list corresponding to the smallest element. Let T(n) denote the running time of this algorithm (we can assume that sqrt(k) is an integer for all k<=n encountered in the algorithm).

Running time : T(n) <= sqrt(n) T( sqrt(n) ) + O(n^1.5)

I can think of it as T(n) = T( sqrt(n) ) + T( n-sqrt(n) ) + O(n) but can't relate to the solution. Plz can anybody explain its running time.