Array merging question, alternate merge

[Mary U]

I've been given two arrays:

arr1 = [1,8,9,12]
arr2 = [2,3,10,11,13]

My task was to merge the two arrays into a third array. Done, no problem, merged then sorted a new array.

I understand there is a way to merge the two without using "merge" then "sort" functions. My reference material doesn't go into it, and I can't find an example of how this would work.

I think there would be a way to do it using a for loop and then "push", but I could be way off.

Can anyone tell me how they could see merging two without using the merge then sort? And what would be the advantage to doing it this alternate way as opposed to using merge? Is there a case where it would be preferable? I'm so new at this that I can't fathom doing anything other than merge.

I would appreciate your thoughts. I'm sure there are a few different ways to do this.

Mary U

[TinyScript]

I just happened to be at a site and
i saw an awesome page of scripts for you to see.

http://jsfromhell.com/array

[Mary U]

That is a very interesting site. There appear to be many interesting scripts on there.

[Philip M]

Mary, I guess what you have now is:-

arr1 = [1,8,9,12];
arr2 = [2,3,10,11,13];
var arr3 = arr1.concat(arr2);
arr3.sort(function(a,b){return a - b});

Javascript has these built-in functions to make life easy. There is no point in making life difficult. concat is just a short form of a for loop + push.


James (007) Bond: (to Bibi) You get your clothes back on, and I'll buy you an ice cream.

[Mary U]

Thank you, Philip. I thought going round the concat and sort functions was a bit ridiculous. The book simply tries to "challenge" us by saying "Try to find a solution in which you do not append the two arrays and then sort the result. Try to examine each element in the array, then push the smaller value." As this is a beginner program, I imagine if I were taking a class the instructor would go over this in class. As I am not in a class, just working through the problems on my own I don't have the answer key.

I could not think of any reason to do it this way, other than to frustrate me of course.

Thank you for your time.

Mary

[Philip M]

I sometimes wonder whether the authors of these textbooks and homework assignments (and some school teachers) have any real understanding of the subject or the assignments they set. The suggested way of merging/sorting two arrays seems to be the equivalent of cutting the lawn with nail scissors.

For your edificaton:-

<script type = "text/javascript">

arr1 = [1,8,9,12];
arr2 = [2,3,10,11,13];

var arr4 = new Array();
var alen = arr1.length;
var blen = arr2.length;
var len = alen + blen;
var max = 99999;

for (var i = 0; i <= len; i++) {

var a = arr1[0];
var b = arr2[0];
if (a == undefined) {a=max}
if (b == undefined) {b=max}

if ((a <= b) && (a < max)) {
arr4.push(a);
arr1.shift();
}


if ((b < a) && (b < max)) {
arr4.push(b);
arr2.shift();
}

}

alert ("FINAL ARRAY = " + arr4)

</script>

[mrhoo]

It is also like counting the cows' hooves and dividing by four and multiplying by their ears and taking half of that to count the herd...

But there is always another, less efficient way to do anything....
EDIT: this method is named slowmerge- it is another way, not a faster way

Array.prototype.slowmerge= function(arr){
	var A= [], item, i;
	A[0]= this.shift();
	while(arr.length){
		i= 0;
		item= this.length? this.shift(): arr.shift();
		while(A[i] && item>= A[i]) i++;
		A.splice(i, 0, item);
	}
	while(A.length) this.push(A.shift());
	return this;
}

var a1= [13,1, 3, 5, 6, 7], a2= [4, 6, 4, 8, 9, 2,10];
alert(a1.slowmerge(a2));

[Mary U]

Philip,

I agree with you, after seeing all the work one would have to do, it does seem rather silly!

I appreciate your help, I'd given up on it. Now I know I would have been monkeying around for about a year before I came up with that.

I think I'm going to play around with it, experiment.

Thank you.

Mary

[Mary U]

mrhoo;

Thank you to you as well, it appears there is more than one way to count the herd.

Mary

[Philip M]

mrhoo;

Thank you to you as well, it appears there is more than one way to count the herd.

Mary

Yes, of course. There are often several or even many different ways in Javascript of achieving the same result. Speed of execution/efficiency is rarely an issue these days, as the differences are often undetectible. I would take the view that four lines of code is better than a dozen, or twenty!

[jkd]

The whole point of this is to implement a merge sort, which is O(N log N), versus a naive sort, which is O(N^2).

If you have two already sorted arrays, of length M and N respectively, merging them into a sorted array is O(N+M) when you make the effort to do it intelligently. Doing a.concat(b).sort() destroys whatever advantage you had beforehand (supposing that the builtin sort() method is O(N log N), then that JS statement costs O((N+M) log(N+M))).

I don't care how fast computers are, an order of magnitude is an order of magnitude, and definitely worth the effort even in this situation.

[Philip M]

The whole point of this is to implement a merge sort, which is O(N log N), versus a naive sort, which is O(N^2).

If you have two already sorted arrays, of length M and N respectively, merging them into a sorted array is O(N+M) when you make the effort to do it intelligently. Doing a.concat(b).sort() destroys whatever advantage you had beforehand (supposing that the builtin sort() method is O(N log N), then that JS statement costs O((N+M) log(N+M))).

I don't care how fast computers are, an order of magnitude is an order of magnitude, and definitely worth the effort even in this situation.

I'll take your word for it. A bit above my head, I am afraid. And just possibly above Mary's head as well. And what if the two initial arrays are unsorted?

So what method or technique are you actually recommending?

[jkd]

If the initial arrays are unsorted, then split them in smaller arrays, sort them, and merge them.

The point is, this is obviously a homework assignment. The professor is hinting at what is known as a merge sort, which basically can be described as follows:

mergesort array =
If array is 1 element, return it. Otherwise, divide the array into 2 as-equal-as-possible subarrays, mergesort both of them. Now, merge both sorted subarrays and return it.

It's a classic recursive algorithm, and it relies on merging the subarrays intelligently, e.g. copying from one until its first element is no longer the smaller of the 2 arrays, then copying from the other until its first element is no longer the smallest, etc.

If you think about it, there are roughly lg(n) divisions starting with an array of n elements, and for each division, you are merging arrays of length n/2 and n/2, exercising a total cost of O(n). Thus, the performance for the entire mergesort is O(n lg(n)).

Pedagogically speaking, it is fairly clear from what the OP posted that this result is what their professor/teacher/book/tutor was getting at -- writing the merge algorithm for the sort. I also took the fact that both the arrays they posted were sorted as further evidence of the intent.

Now, what I'm suggesting is a simple algorithmic improvement. Yes, it's no longer a one-liner, but it is far more elegant and efficient algorithmically.

[Philip M]

If the initial arrays are unsorted, then split them in smaller arrays, sort them, and merge them.

The point is, this is obviously a homework assignment. The professor is hinting at what is known as a merge sort, which basically can be described as follows:

mergesort array =
If array is 1 element, return it. Otherwise, divide the array into 2 as-equal-as-possible subarrays, mergesort both of them. Now, merge both sorted subarrays and return it.

It's a classic recursive algorithm, and it relies on merging the subarrays intelligently, e.g. copying from one until its first element is no longer the smaller of the 2 arrays, then copying from the other until its first element is no longer the smallest, etc.

If you think about it, there are roughly lg(n) divisions starting with an array of n elements, and for each division, you are merging arrays of length n/2 and n/2, exercising a total cost of O(n). Thus, the performance for the entire mergesort is O(n lg(n)).

Pedagogically speaking, it is fairly clear from what the OP posted that this result is what their professor/teacher/book/tutor was getting at -- writing the merge algorithm for the sort. I also took the fact that both the arrays they posted were sorted as further evidence of the intent.

Now, what I'm suggesting is a simple algorithmic improvement. Yes, it's no longer a one-liner, but it is far more elegant and efficient algorithmically.

Seems a bit difficult for a beginner such as Mary. More of a (maths) graduate level assignment.

What you call a mergesort (which appears to be select the smallest first element of the two arrays) seems to be in effect what I cobbled up in post #6 just to show Mary how crude and inefficient that was compared with concat + sort in Post #4. We live and learn! And I am sorry to say that your idea of elegance is not the same as mine!

But I stick with my point - unless very large arrays are involved, the theoretical efficiency of the method does not really matter a jot. The difference between (say) 2 milliseconds and 10 milliseconds is not perceptible.

[Mary U]

Thank you for the discussion.

If mergesort is what the material was striving for then perhaps I need to stop working on this now, it wasn't/isn't mentioned anywhere in the book/materials.

Looking ahead in the materials I do see where recursive algorithms are covered, and to be honest now I am a bit scared because I read through jkd's post several times and still don't think I grasped it all.

As there was no published answer, I assumed the answer was fairly simple, and was merely an alternate method of accomplishing what I already had, perhaps the mergesort is simple, but it doesn't seem that way to me, at least not yet.

Mary