merge sort

zap

can someone explain how a merge sort works, has anyone any examples?

satchmo

There's a very good explanation here with Java source.

zap

ok i get say that you have

an array 1 5 6 7 8 9

so that gets split into

1 5 6 and 7 8 9


where do i go after that?

1 5 6 splits into

1 5 6

then


1


is that correct

pH

Basically you code it as a recursive function

sort(array) {
if (arraylength = 1) return

sort(1st half)
sort(2nd half)
merge(1st half, 2nd half)
}

Each 1/2 gets fired back into the 'sort' algorithm, you keep splitting in half and merging until each half only has one element in it.

You don;t actualy write a 'sort' the only thing that matters is the merge, which basically has 2 ordered lists and has to make one ordered list from both parts. There are a number of ways of writing the merge more efficiently.

Skud

http://math.hws.edu/TMCM/java/xSortLab/

This should help you out. Explains the visual worikings of some common sort algorithms