user4171112 February 2016

Merge two sorted arrays in runtime faster than O(N)

I think I have a solution but I am not completely sure.

My solution was to Convert Arrays to Linked Lists. Then Merge and sort the linked list recursively.

I've read that it will take O(1) space in memory. But I am not sure the runtime would be faster than linear time.

Any suggestions please?

Answers


chqrlie February 2016

There is a special case where you can merge 2 arrays in constant time:

  • The arrays are adjacent, that is they are slices of the same array and the last element of the first is just before the first element of the second.
  • The last element of the first array is less or equal to the first element of the second array.

The case can be checked with a single test.

This may seem ludicrous, but it is a very common case for mergesort and testing for this special case first increases mergesort performance significantly for arrays that are already fully or partially sorted. A similar test can be used to handle arrays that are sorted in reverse order, and carefully crafted code can achieve O(N) sorting times for both sorted and reverse sorted arrays while keeping the same number of element comparisons for the general case.


djechlin February 2016

My solution was to Convert Arrays to Linked Lists.

That takes O(N) time and memory.

Post Status

Asked in February 2016
Viewed 1,172 times
Voted 4
Answered 2 times

Search




Leave an answer