Implement bottom-up mergesort

degree of difficulty: 2 (only if you already have implemented the merge step)

Bottom-up mergesort is a non recursiv mergesort variant.

In the first pass all 1-1-pairs of consecutive elements are merged together. In the next pass all 2-2-pairs of consecutive elements are merged, and so on, until in the last pass all elements are merged into one sorted sequence:

2 | 5 | 9 | 2 | 1 | 5 | 3 | 7 | 9 | 0 | 2 
2   5 | 2   9 | 1   5 | 3   7 | 0   9 | 2  after first pass
2   2   5   9 | 1   3   5   7 | 0   2   9  after second pass
1   2   2   3   5   5   7   9 | 0   2   9  third pass
0   1   2   2   2   3   5   5   7   9   9  last pass

Solution

Implement Shell sort

degree of difficulty: 1

Shell sort is a refinement of insertion sort. It was published 1959 by D. L. Shell. Shell sort applies insertion sort multiple times with decreasing gap size k. In the last pass k always is one. For instance, in the first pass k = 4: insertion sort is applied to every fourth element of the array. There are four such subsequence (starting at position 0, 1, 2, and 3). For a given k, this pass of insertion sort is called k-sorting. The next pass might by a 2-sorting and finaly a 1-sorting which is an ordinary insertion sort.

Lets have a look at an example with eight numbers. We apply a 4-, 2-, and finally a 1-sorting on the array. The subsequences are emphasized by colors.

58371624Unsorted array with gaps of four
18375624Insertion sort on the yellow subsequence
16375824Sorting cyan" subsequnce
16275834Sorting all "white" elements
16245837Sorting all "orangen" elements

We always had the worst case of insertion sort: the elements of the colored sequences have been ordered in descending order. For each subsequnce four comparision have been necessary to sort them. However, smaller numbers have been exchanged by larger numbers via the gap size 4. In the result, smaller numbers now tend to be in the first half of the array, larger number in the second half: a step to the best case of insertion sort. We now apply a 2-sorting.

16245837Array after the 4-sorting step
16243857
14263758

Note that due to the first 4-sorting step only few comparision and exchanges have been made by the 2-sorting step. The final step is a normal insertion sort (1-sorting):

14263758Start
14263758
12463758
12463758
12346758
12346758
12345678
12345678

In the last pass only 9 comparisions have been necessary to sort the array. In the worst case insertion sort needs 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 comparisions. Shell sort systematically rearranges the order in the array such that for subsequent k-sorting steps the worst case becomes less likely. The overall running time depends of the choice of the k-sorting steps. For the sequence k = 2log2n, ..., 63, 31, 15, 7, 3, 1 shell sort performes with O(n1,5) comparisions in the worst case. Currently the best known sequence leads to O(n(log2n)2) running time.

Implementt Shell sort for the above sequence. Note that the last sorting always is insertion sort: even if your program has bugs in k-sorting steps, the final correct insertion sort leads to a sorted array, but the performance may still be O(n2) or worse. Implement the k-sorting step as a public methode (due to it would be private) and test it thorougly.

Solution

Natural Mergesort

degree of difficulty: 1

Implement Natural Mergesort in Java

Natural mergesort is an improved variant of bottom-up merge sort. Instead of merging first 1-1-pairs, the 2-2-pairs and so on, natural mergesort merges two already sorted paired subsequences.

Lets consider 7 4 6 3 1 2 8 5 as an example. This sequence already contains sorted subsequences. We indicate these with |: 7 | 4 6 | 3 |1 2 | 8 | 5 . Natural mergesort has to find these subsequence and all pairs of these sequence are merged. Then again pairs of sorted subsequences are merged together until the whole array is sorted.

7 | 4 6 | 3 |1  2 | 8 | 5
4 6 7 | 3 | 1 2 | 8 | 5
4 6 7   1 2 3 | 8 | 5
4 6 7 1 2 3 5 8   <-- after first pass
 
4 6 7 | 1 2 3 | 5 8
1 2 3 4 6 7 | 5 8 <-- after second pass
 
1 2 3 4 5 6 7 8   <-- after third pass

Give the running time in the worst and best case?

Solution