Java recursive and iterative merge sort

Recursive version

Divide and conquer - split into two parts arbitrarily, sort both parts and then merge them together to complete the sort.

There are two ways of splitting, odds and evens or left and right, leading to quite different implementations. There is also an approach called natural merge sort where we make use of

existing sorted (and/or reverse sorted) sequences.

The following outlines the left-right method which will be more efficient if the data structures exceed the amount of physical memory. Also if the left element is always merged before

the right element when they compare equal, the algorithm will be stable (not mess with the order of equal elements).

Note that there is a redundant copy after each merge - it is possible to avoid this by swapping which is source and which is target each time (one mark off for excessive copying).

mergeSort(objects, left, right)

1. declare a second array of the same size to use for merging;

2. define the left and right bounds of the array defining a subarray;

3. if there are less than two elements there is nothing to do and the subarray is sorted;

4. if there are two or more elements,

- sort the left subarray and the right subarray this way;

- merge the sorted subarrays into the second array;

- copy the merged subarray back into the original array.

merge(a, b, left, right, size)

1. initialize target = left, lbound = right, rbound = size

2. while left < lbound and right < rbound

- if a[left] <= a[right], move it to b[target] and increment left and target

- else a[right] < a[left], move it to b[target] and increment right and target

3. move across the rest of whichever side hasn't been copied yet.

Iterative version

Hint. You don�t actually need a stack and will get an extra mark if you avoid it. The splitting is purely conceptual - nothing changes in the array until you merge. Initially you will be merging single elements into pairs, then pairs into quads, then quads into octets, ... You might likely to consider in the recursive versions of quicksort and mergesort just where the

work happens (on the way in or the way out). This also relates to the idea of top-down and bottom up. In iteration you don�t need to model both halves of the recursive process

(down/into deeper levels and up/out of the deeper levels).

In producing an iterative version you may find it convenient to assume y

Algoritmus Java

Projektazonosító: #19300680

A projektről