Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Merging two arrays  RSS feed

 
Aron Silvester
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm reading about the merge sort. In order to merge two arrays, first you'll need to sort those two arrays separately, after sorting the two arrays compare an entry from array1 with an entry from array2 and copy the smaller entry to the new third array. But if you were using the merge sort for just one array, then you wouldn't necessarily need an extra array. This is what I got from reading my book. Is this right?
 
Les Morgan
Rancher
Posts: 768
19
C++ Java MySQL Database Netbeans IDE Oracle Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you have just one array, then what do you have to merge? And if you have to sort the array before you can merge, but you only have one array, then it's already sorted to start with.
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
merge sort basically divides an array in 2 parts and then first sort them individually then merge both of them.
 
Les Morgan
Rancher
Posts: 768
19
C++ Java MySQL Database Netbeans IDE Oracle Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But then you are back to 3 arrays... the op's question was what if you have just one, then you wouldn't need that extra array... so again I ask--what is it that you are going to merge when you only have 1 array?

OK, I suppose you could logically split the first array by choosing the median point and working from the beginning to it and from the median to the end.

Tushar Goel wrote:merge sort basically divides an array in 2 parts and then first sort them individually then merge both of them.
 
Stephan van Hulst
Saloon Keeper
Posts: 7803
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think the original question is about using an "in-place merge sort". In this case, you don't need an extra array, because the two original arrays are merged together into the original array.

If you don't do an in-place merge sort, you need at least half an extra array for merging.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:I think the original question is about using an "in-place merge sort"...

@Aron: which is actually quite tricky.

The way merge sort (at least a "bottom up" merge sort, which is the one I remember) usually works is this:
1. Assume you have an array call 'unsorted'.
2. Allocate another array called 'sorted' of the same size.
3. Divide 'unsorted' logically into adjacent groups of length 1 (which must by definition be "sorted").
4. Merge each pair of adjacent groups in 'unsorted' into a group of twice the length, and put the result in 'sorted'.
5. If the length of your 'sorted' groups are less than unsorted.length:
  5a. Copy 'sorted' to 'unsorted' (or just swap the references around).
  5b. Multiply the group length by 2.
  5c. Go back to Step 4.

That way, each "merge" step is guaranteed to be working with two sorted groups; and in the case of an "odd" group at the end of the array, it is simply merged with an "empty" (or smaller) group to it's right - but the merge logic is the same in every case.

HIH

Winston
 
Campbell Ritchie
Marshal
Posts: 55681
161
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I merged your stuff with the following thread. I hope that is okay by you.
 
Aron Silvester
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In my book it says that "Imagine that you have two distinct arrays that are sorted. Merging two sorted arrays is not difficult, but it does require an additional array". Then I was browsing some forum and someone said, "If two arrays contains suffiecient space for sorting additional data then does not require an additional array for merge the two arrays."

Bottom line is, I'm confused. Can someone shed light to this???
 
Campbell Ritchie
Marshal
Posts: 55681
161
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please tell us the name of the book.

I think this question should be added to your existing discussion. It is a case of merge sort in place and merge sort not in place, which have already been mentioned.
 
Les Morgan
Rancher
Posts: 768
19
C++ Java MySQL Database Netbeans IDE Oracle Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To me it seems silly to have "sufficient space" in an existing populated array to be able to merge, but indeed you can and there are a few way to approach it. The most direct, IMO, being:

take the array you are going to use for the destination and move the existing data to the end, so you have an array that now runs from N-k, to N--where k is the population size of the array. Next you do your standard merge sort, starting at element 1 of the array you are populating. Once the destination array has the merged data, you can "clear", what ever that may entail, the existing elements that you moved to the end of the array.

IMO, much better to use a collection and just use the sort method, or a db if you have large data.

Aron Silvester wrote:In my book it says that "Imagine that you have two distinct arrays that are sorted. Merging two sorted arrays is not difficult, but it does require an additional array". Then I was browsing some forum and someone said, "If two arrays contains suffiecient space for sorting additional data then does not require an additional array for merge the two arrays."


Bottom line is, I'm confused. Can someone shed light to this???
 
Campbell Ritchie
Marshal
Posts: 55681
161
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Les Morgan wrote:. . . Bottom line is, I'm confused. Can someone shed light to this???
If we had the name of the book and page number, it might be easier to understand.

I think you had the quote tags in the wrong place; I have corrected that.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Les Morgan wrote:Bottom line is, I'm confused. Can someone shed light to this???

As Stephan suggested, I believe it's possible to do a merge "in-place" (ie, with minimal space overhead), but it's quite a bit trickier than with a target array; and it involves swapping contents - each of which requires 3 distinct 'moves' - as opposed to simply moving a value to the target once you know where it needs to go.

@Aron: And don't forget that in Java, arrays of "objects" are actually arrays of references, so in fact the space you're duplicating is only 4 or 8 bytes for each element, rather than the space for the objects themselves (which are almost certainly much bigger).

Don't know whether it answers your question, but HIH.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!