CODEWITHSUNDEEP
algorithmsorting
mmostajab
mmostajab

Reputation: 2037

Inset number from a non-sorted list of numbers into a sorted list of number

I have a list A which its elements are sorted from smallest to biggest. For example:

A = 1, 5, 9, 11, 14, 20, 46, 99

I want to insert the elements of a non-sorted list of numbers inside A while keeping the A sorted. For example:

B = 0, 77, 88, 10, 4

is going to be inserted in A as follows:

A = 0, 1, 4, 5, 9, 10, 14, 20, 46, 77, 88, 99

What is the best possible solution to this problem?

Upvotes: 0

Views: 86

Answers (2)

Chasefornone
Chasefornone

Reputation: 757

Best solution depends on how you define the best.

Even for time complexity, it still depends on your input size of A and B. Assume input size A is m and input size of B is n.

As Salvador mentioned, sort B in O(nlogn) and merge with A in O(m + n) is a good solution. Notice that you can sort B in O(n) if you adopt some non-comparison based sort algorithm like counting sort, radix sort etc.

I provide another solution here: loop every elements in B and do a binary search in A to find the insertion position and then insert. The time complexity is O(nlog(m + n)).

Edit 1: As @moreON points out, the binary search and then insert approach assume you list implementation support at least amortized O(1) for insert and random access. Also found that the time complexity should be O(nlog(m + n)) instead of O(nlogm) as the binary search took more time when more elements are added.

Upvotes: 1

Salvador Dali
Salvador Dali

Reputation: 222521

Best possible is too subjective depending on the definition of best. From big-O point of view, having an array A of length n1 and array B of length n2, you can achieve it in max(n2 * log(n2), n1 + n2).

This can be achieved by sorting the array B in O(n log n) and then merging two sorted arrays in O(n + m)

Upvotes: 3

Related Questions