Exercise 1 - Ternary search¶

The BINSEARCH procedure searches a sorted array A[1..n] for the number key using a binary search. In a binary search the starting array A[L..R] is divided into two (nearly) equally sized subarrays at each iteration (or recursion level): A[L..mid] and A[(mid+1)..R]. By comparing the element at the split point, it can be deduced whether the search should continue in the left or right half (unless the split point contains the element we search for).

In a ternary search a similar approach is used, except that at each iteration (or recursion level) the starting array A[L..R] is divided into three (nearly) equally-sized subarrays: A[L..mid1], A[(mid1+1)..mid2] and A[(mid2+1)..R]. The number key can occur in only one of these three subarrays and hence the other two can be discarded.

Write a procedure TERNSEARCH using a ternary search approach that is an alternative to BINSEARCH.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

BINSEARCH(A,L,R,key)
  input A[1..n] is an array containing numbers; L and R are the
  leftmost and rightmost indices that concern us; key is the value
  we want to find
  output: the index at which key occurs in A, or -1 if it doesn't
  /* The numbers in A must be in order from smallest to largest.
  We search in array A[L..R] for key. If key is found, we return
  its location, otherwise we return -1.*/
  if L == R then
    if A[L] == key then
      return L
    else
      return -1
    end
  else
    mid = floor( (L+R)/2 )
    if key <= A[mid] then
      return BINSEARCH(A,L,mid,key)
    else
      return BINSEARCH(A,mid+1,R,key)
    end
  end

Exercise 2 - Natural mergesort¶

In this problem we will use the following array an example: A[12, 14, 5, 3, 7, 20, 16, 9], index i goes from 1 to 8. The goal in this problem is to write pseudocode for a natural mergesort algorithm, in which the elements of some array A[1..n] are put in order from smallest to largest. To understand how a natural mergesort works, one must understand what a decreasing inversion is and what a run is. In an array, which we want to be sorted in increasing order, there is a decreasing inversion at location i when A[i] > A[i+1]. A run is some subarray, in which all the elements are in increasing order. The end of a run always occurs at a decreasing inversion. For example the above array can be broken into 5 runs as follows:

run    run elements
1   [12,14]
2   [5]
3   [3, 7, 20]
4   [16]
5   [9]

In a natural mergesort, we first merge runs 1 and 2, then runs 3 and 4, then runs 5 and 6 and so on, until we have reached the final run. After this merging is done we will have (roughly) half the runs remaining that we started with. We again merge the new runs: runs 1 and 2, runs 3 and 4 and so on. We continue merging the runs until there is only one run left. A description of how natural mergesort works is given in algorithm NATMERGESORT:

NATMERGESORT(A)
1. Start from A[1] find the locations of the decreasing
inversions.  Based on these locations find the start and
end of all the runs.
2. Merge runs 1 and 2, runs 3 and 4, runs 5 and 6 and so
on until no more runs are left to be merged.
3. Repeat step 2, until only one run remains.

Using algorithm NATMERGESORT on the above array, would produce the results given in the following table:

stage  step  runs formed
  1   1  [12,14], [5], [3, 7, 20], [16], [9]
  2   2  [5, 12,14], [3, 7, 16, 20], [9]
  3   2  [3, 5, 7, 12,14, 16, 20], [9]
  4   2  [3, 5, 7, 9, 12, 14, 16, 20]

Task: Write pseudocode that implements algorithm NATMERGESORT.