2

We get O(m+n) on merging 2 sorted arrays if we are allowed to use O(n) extra space of temporary array. So all elements are merged into one temporary array.

But, how to perform merging if I am only allowed to use O(1) extra space?

mort
  • 12,988
  • 14
  • 52
  • 97
Garrick
  • 677
  • 4
  • 15
  • 34
  • 3
    You don't need hash table for sorted arrays merging, and space is needed only for resulting array. – MBo Sep 01 '16 at 01:41
  • 1
    Where should the merged contents, i.e. m+n elements, be kept? – Arun Sep 01 '16 at 01:46
  • They can be kept in any array – Garrick Sep 01 '16 at 01:48
  • 1
    you nd to be more specific with memory allocated. are you given two arrays or just one array with m+n entries. your O notation is all for time complexity? – softwarenewbie7331 Sep 01 '16 at 02:04
  • I have edited. see now – Garrick Sep 01 '16 at 02:06
  • 4
    In-place merge algorithms exist, but simple ones reveal significantly worse behavior, others are too complex to implement. http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm – MBo Sep 01 '16 at 02:47
  • What has your research discovered? Have you not come up with *any* possible approaches? Please note the tooltips when you hover over the up and down vote arrows next to your question. – beaker Sep 01 '16 at 14:55

1 Answers1

2

Yes it is possible to merge two sorted arrays with O(1) extra space.

We can achieve this by using Insertion sort.

But the time complexity to merge two sorted arrays using O(1) extra space would be O(n^2).

If We allowed to use O(n) extra space, then we can use Merge sort with time complexity of just O(nlogn).

Durgesh
  • 37
  • 4