• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Merging two arrays

 
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Rancher
Posts: 1059
27
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 1059
27
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.

 
Saloon Keeper
Posts: 14508
325
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Marshal
Posts: 76885
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 76885
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 1059
27
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 76885
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Enjoy the full beauty of the english language. Embedded in this tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic