0

I was asked this in an interview related to C#. There are 2 arrays - presorted from lowest to highest. I need put all of these combined in a 3rd array and they should be inserted in a sorted manner (as they are going in).

The solution I mentioned was as below:

  1. For argument sake lets say Array 1 has the following elements - 1,2,3,4,5 and Array 2 has the following elements - 6,7,8,9,10

  2. Since the 2 arrays are pre-sorted - you would compare the first element of Array 1 to the first element of Array 2 and the insert the lower element in Array 3.

  3. You would then do the same for Element 2 of Array 1 and Element 1 of Array 2 and pop in the next smallest number

The approach which I mention should work - but the questions I have are as follows:

  1. Is this the most efficient approach?
  2. Are there technical term (like Binary Search Algo etc etc) which can describe this process?
  3. Any other pointers for this problem on solving?
Improve this question
1
  • Yeah, this is the merge part of mergesort. Commented Mar 21, 2013 at 20:34

3 Answers 3

Reset to default
3

Yes, this is the most efficient approach.

It runs on O(n) (where n is the size of both arrays) which means going through the arrays once.

In order to create the third array you would have to go through each element once anyway (even if it is just to add it to the third array in the correct order).

This process is usually called merge and it is part of the Merge Sort algorithm.

Here is an implementation right here in Stack Overflow.

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

3 Comments

Benjamin -Thanks this helps a lot. Just looked a visualization on wikipedia - en.wikipedia.org/wiki/Merge_sort and makes it crystal clear now. Are there are such common algorithms which I should be aware of - C# perspective and interview perspective. Any pointers will help
@Patrick It's a very broad questions. In my experience people love asking about binary tree algorithms (building a tree, avl trees, deleting a node), Sorts (merge sort, quick sort, heap sort), Dynamic algorithms (See "google polygon" answer in my previous answers in SO. That really depends on the position you're interviewing for, my best advice would be to read up a lot on interview questions and in general do a lot of interviews. If you worked this out on your own during the interview I think you're doing OK :) If this answer solved your problem please consider accepting it.
Yes - worked it out during the interview after going back and forth :). Waiting for the time to expire to say accept this as an answer. Thanks a lot
1

1) It's the most efficient approach, O(n+m). Where n - size of the first array, m - size of the second array. 2) It's called merge routine of the Merge sort algorithm.

Actually you can merge more than 2 arrays, usually it's used in External sorting or when you have space limits.

Improve this answer

Comments

1

  1. If you know the input arrays are sorted, then a merge algorithm would be linear (O(n) in Big O notation). However, if you also know that the maximum value of one of the arrays is lower than the minimum value of the other, you can use Array.Copy instead of comparing individual elements for even better performance.

  2. Yes, this is a merge algorithm.

  3. Practice makes perfect. I like solving Project Euler problems for fun - they are "small" but once you get past the first few they'll really make you think about how to solve it.

    Edit for flair: pointless

Improve this answer

1 Comment

Thanks. I had taken an example where Array 1 elements (in sorted fashion) where smaller than Array 2. But that was an simple assumption. Merge Sort looks like a perfect Answer - just that I didnt know about the name

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.