• Post Reply Bookmark Topic Watch Topic
  • New Topic

Implementing Merge sort algorithm  RSS feed

 
Paul Ngom
Ranch Hand
Posts: 355
1
  • Mark post as helpful
  • send pies
  • 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

 
Stephan van Hulst
Saloon Keeper
Posts: 7991
143
  • Mark post as helpful
  • send pies
  • 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?
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • 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
  • 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.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • 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
  • 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.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • 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
  • 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
 
Paul Clapham
Sheriff
Posts: 22832
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • 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
  • 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: 42972
73
  • Mark post as helpful
  • send pies
  • 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
  • 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: 42972
73
  • Mark post as helpful
  • send pies
  • 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
  • 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: 42972
73
  • Mark post as helpful
  • send pies
  • 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
  • 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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!