programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Implementing Merge sort algorithm

Paul Ngom
Ranch Hand
Posts: 355
1
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
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
Wirth's classic Algorithms and Data Structures discusses various variants of Merge Sort in detail.

Paul Ngom
Ranch Hand
Posts: 355
1
@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
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
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
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
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
"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
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
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
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
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

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
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
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.