You shouldn't allocate memory for auxiliary array every time in your recursive method. You allocate this array O(K*log(N)) times. Try to allocate it only one time.