Sort array (Time complexity )

Question

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?

O((m+n) log (m+n)). If you use a standard library function, this bound is exact, and you can't get much better anyways. — John Dvorak
– John Dvorak, Commented Feb 2, 2013 at 0:24

rob mayoff · Accepted Answer · 2013-02-02 00:31:49Z

4

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).

answered Feb 2, 2013 at 0:31

rob mayoff

387k69 gold badges842 silver badges887 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

John Dvorak Over a year ago

M is the size of the unsorted part

rob mayoff Over a year ago

Yes, I realized that I misread the problem and fixed my solution.

John Dvorak Over a year ago

Note that O(M + M log M)=O(M log M), meaning that you can simplify the complexity expression.

user1951891 Over a year ago

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

rob mayoff Over a year ago

If you can merge two sorted arrays in linear time and constant additional space, you won't change the complexity. This paper claims to describe such an algorithm, but I've only read the abstract.

Collectives™ on Stack Overflow

Sort array (Time complexity )

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related