CODEWITHSUNDEEP
arrayssortingbig-otime-complexity
user1951891
user1951891

Reputation: 11

Sort array (Time complexity )

if I have an array with cells 0-N that sorted, and cells N+1 until M+N, not sorted. what will be the best time complexity to sort the array?

thanks!

Edit:

thanks !! If I want to do that in-place, it will change the complexity?

Upvotes: 1

Views: 2376

Answers (1)

rob mayoff
rob mayoff

Reputation: 385610

First, sort just the M unsorted elements. This takes time O(M log M) using a comparison-based sort (like quicksort, merge sort, or heap sort).

Then merge the two sorted segments (of lengths N and M) together. This takes time O(M + N).

So the best time complexity, using a comparison-based sorted, is O(M + N + M log M).

Upvotes: 4

Related Questions