• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Implementing Merge sort algorithm

 
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi all,
I will be so grateful if somebody could take me through the Merge sort implementation on
the given array i listed in the code below. I know Arrays.sort() or Collections.sort() could do the trick
but i want to achieve it through merge sort. Please write simple code easy to follow.
Kind regards

 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Paul,

I'd like to point out that we're NotACodeMill.

Can you explain to us in simple English how merge sort works, according to you?
 
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wirth's classic Algorithms and Data Structures discusses various variants of Merge Sort in detail.
 
Paul Ngom
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Ulf
Thanks a lot for the link. I did learn new things there.

@Stephan
My understanding of the merge sort is that an initial array that is to be sorted is split into subarrays that are in turn sorted and combined again in an ordered manner.
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Nearly but not quite. The original array is split until the pieces are so small that they do not need sorting. Then you merge them all back to create a new array.
 
Paul Ngom
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Campbell,
It is worth mentioning that the smallest piece has 1 element and the subarrays are sorted and combined until it remains only one resulting array which is sorted.
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You don't necessarily have to split until you have arrays of size 1. If you have an array of size 2, then it is quicker
to sort it 'by hand' then to split it up again and going into yet another recursion. You could set a threshold and test
for what minimum size it is wise to use some other method to sort.

Greetz,
Piet
 
Paul Ngom
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Pict,
What do you mean by 'sort by hand'?
Have you read the array that I have supplied?
What is the next step?
Kind Regards
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"Sort by hand" means "sort by some method other than merge sort". For example as Piet suggested it's easy to sort an array of size 2 directly by comparing the two elements and swapping them if necessary, and that could well be faster than putting the 2-element array through the merge sorting process. Likewise it might be more effective to sort a 3-element using some cruder sort (even bubble-sort!) rather than merge-sorting it. You'd have to do some careful benchmarking to see whether that's the case, though.
 
Paul Ngom
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Paul,
It is good to read you.
Thanks a lot for the explanation. I want to
merge sort the array that I have provided
in my first post.
Kind regards
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, I think that came across. But what exactly is the problem you're facing? If you understand Merge Sort, what prevents you from implementing it?
 
Paul Ngom
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Ulf,
Thanks for your reply. So far this is what i have and it is not working as i expect:

The final list is not sorted.
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't see any comparison of elements being done anywhere. If you merge two lists you successively add the smaller element of the front of each sublist. But all this code does is to split a list into two halves, and then add them back together. From a quick glance, I think it will just return the original list.
 
Paul Ngom
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


From a quick glance, I think it will just return the original list.


You are right, that is exactly what it does and that is not what i want. Any guidance towards the solution will be most welcome.
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Start with this:

Ulf Dittmer wrote:I don't see any comparison of elements being done anywhere. If you merge two lists you successively add the smaller element of the front of each sublist.


In Wirth's book, section 2.4.1, that's discussed on page 65 in the paragraph starting "In the further refinement step the actual merge statement is to be formulated."
 
Paul Ngom
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was able to get some working code after net searches. Here it is:

Is this done right? I think this is a top down implementation.
reply
    Bookmark Topic Watch Topic
  • New Topic