Contents

1 About this module

• Prerequisites: 0077
• Objectives: This module discusses the non-recursive (iterative) merge sort algorithm.

2 Non-recursive merge sort

In module 0077, we have already explored the non-recursive merge sort in terms of an example to show how it works. Here, we begin with the algorithm, then we will do some analysis on the algorithm.

2.1 Split

Listing 1 is the split algorithm as a subroutine in pseudocode.

In listing 1, we rely on a FIFO data structure. The methods for a FIFO are as follows:

• rewind: prepare to read a FIFO from the beginning.
• rewrite: empty a FIFO (and get ready for writing).
• isempty: indicate whether a FIFO is empty (at its end).
• head: peek and return the value at the head of the FIFO, do not remove the first item.
• remove: remove the first item from a FIFO, and return its value.
• append: append a value as the last item of a FIFO.
• close: finalize operations

The split operation reads from the input FIFO in, then output consecutive runs to the two output FIFOs in an interleaved way. Whenever a run is broken, as detected on line 11, the pointers to the output FIFOs are swapped. This ensures that we only want to output to the FIFO pointed to by out1.

2.2 Merge

Listing 2 is the merge algorithm as a subroutine.

The merge algorithm is a little more complicated than the split algorithm. Much of the logic is captured by the lookup array. This array is three-dimensional, but each dimension is only a Boolean.

The first index indicates whether lastValue is less than or equal to the head of the first input FIFO. If this is true, it means the head of the first input FIFO is a candidate as the next value to append to the output FIFO.

The second index indicates whether lastValue is less than or equal to the head of the second input FIFO. Again, if this is true, the head of the second input FIFO is a candidate to be next value appended to the output FIFO.

The third index indicates whether the head of the first input FIFO is less than or equal to that of the second input FIFO. This is useful when the heads of both input FIFOs are candidates, or when both of them are not candidates.

The initialization of this lookup array handles all the possible cases:

• true, true, true: both input FIFOs are candidates, but we use the first one because it is smaller (or the same)
• true, true, false: both input FIFOs are candidates, but we use the second one because it is smaller
• true, false, ?: the first input FIFO is a candidate, the second one is not. We choose the first one.
• false, true, ?: the first input FIFO is not a candidate, the second one is. We choose the second one.
• false, false, true: both input FIFOs are not candidate, we break a run. However, the first input FIFO is smaller (or the same as the second one), we choose it.
• false, false, false: both input FIFOs are not candidate, we break a run. However, the first input FIFO is larger, we choose the second input FIFO.

The values of the lookup array simply indicates the index of the input FIFO to use.

The conditions on lines 24 and 26 checks to see if a FIFO is empty. If so, use the other FIFO. Because of the precondition of the loop, we are guaranteed that at least one FIFO is not empty.

The actual operations are specified on lines 33 to 35. First, we maintain the sorted status of the output FIFO. This can be done by comparing what we are about to append to the last value appended. Next, we remember the value to be appended as the “last value”. Then, we append the value to the output FIFO.

Because we keep track of whether the output FIFO is sorted, we can return the value of the local variable sorted to indicate whether the output FIFO is sorted.

2.3 Mergesort

Once we define the merge and split operations, then we can define the merge sort algorithm itself in listing 3.

This algorithm is rather simple. All we have to do is to keep split-merging until the merged result is sorted.

3 Data structure

This section deals with the mysterious FIFO type.

3.1 What is it?

The FIFO type is an abstraction of data types that have the first-in-first-out nature. The queue abstract data type fits in this category. However, a sequential file also does. This is because when a sequential file is opened for reading, we can only read in one direction. When a sequential file is opened for writing, we can only write in one direction (same direction as reading).

This is why there are the rewind, rewrite and close methods.

3.2 Linked list queue

A queue abstract data type is a FIFO. The translation of a queue ADT to a FIFO is straightforward. Some FIFO methods are not applicable to queues.

3.3 File

To abstract a sequential file as a FIFO, we need a little bit of work.

• rewind: this is for (re)opening a file for input, and place the file pointer at the beginning of the file.
• rewrite: this is for (re)opening a file for output, and place the file pointer at the beginning of the file.
• close: this is for closing a file.
• remove: this operation actually perform a file read operation, move the file pointer (implicitly), and return the value read.
• append: this is just writing the value to a file opened for sequential write access.

3.4 Buffered read

The head method allows the algorithm to “peek” the first item of a FIFO without removing it. Neither the ADT of a queue nor file operations implement this kind of operation.

As a result, the FIFO implementation needs some additional data members. First of all, as we rewind a FIFO, we need to follow the buffered read logic in listing 4 after performing the implementation dependent rewind operation (reopening a file, for example).

The FIFO head method just needs to return the data member buffer.g.

The FIFO remove method needs use buffered read. However, it needs to remember the value to return first, otherwise the buffered read operation overwrite the value to be returned. The logic of FIFO remove is listed in listing 5

The FIFO isempty is not a wrapper of the isempty method of the implementation. This is because we are performing buffered read. The actual implementation may be empty, but the FIFO itself may not be empty yet, because the last item in the actual implementation is actually stored in the data member buffer. In other words, FIFO isempty is always behind the implementation isempty by one read.

4 How long does it take?

4.1 Split

The split subroutine reads every value from the input FIFO, and outputs every value to one of the two output FIFOs. As a result, the amount of of time required by each invocation of “split” is proportional to the number of items to sort.

4.2 Merge

The merge subroutine reads every value from the two input FIFOs, and outputs each value to the output FIFO. As a result, the amount of time required by each invocation of “merge” is proportional to the number of items to sort.

4.3 Mergesort

How many iterations do we need? That’s the real question. Each iteration of the loop in “mergesort” calls split and merge each once. In other words, the execution time of each iteration of the loop in mergesort is proportional to the number of items to sort.

The question boils down to how quickly the algorithm reduce the number of runs in the worst case.

4.3.1 Merging two runs

A run can be considered as a tuple $\left(a_1,a_2,a_3,\dots a_n\right)$. By definition, elements in a run are sorted. In our example, $\forall i,j\in \left[1\dots n\right]:\left(i\le j\right)\Rightarrow \left(a_i\le a_j\right)$, assuming the tuple is sorted in a non-decreasing way.

Now, let us consider two runs, $A=\left(a_1,\dots a_n\right)$ and $B=\left(b_1,\dots b_m\right)$. We claim that after we merge there two runs, the result is a single run with $n+m$ values.

How do we prove this?

Let us use proof-by-contradiction. We first negate the proposition that we want to prove, yielding “$\left(a_1,\dots a_n\right)$ and $\left(b_1,\dots b_m\right)$ are two runs, after the merge process, the result is not a single run.”

Let us symbolically represent the merge result as $C=\left(c_1,\dots c_{m+n}\right)$. Let us define the first break point of the run as $\exists i\in \left[1\dots m+n-1\right]:c_i>c_{i+1}\wedge \neg \left(\exists j\in \left[1\dots i-1\right]:c_j>cj+1\right)$. Let us assume $c_{i+1}$ corresponds to $b_q$.

Furthermore, let us define $p$ as follows: $p=min\left(j:c_j>c_{i+1}\right)$.

At this point, we have the sequence like this:

$\left(c_1,c_2,\dots ,c_p,c_{p+1},\dots ,c_i,c_{i+1},\dots ,c_{m+n}\right)$ in which $c_i>c_{i+1}$ and $c_p>c_{i+1}$.

If one of the $c_j,j\in \left[p\dots i\right]$ comes from run $B$, we have a contradiction because run $B$ is sorted.

If all of the $c_j,j\in \left[p\dots i\right]$ come from run $A$, we still have a contradiction. Let $c_p$ correspond to $a_r$. When we choose the value of $c_p$, the two candidates must have been $a_r$ and $b_q$. We know that neither $a_r$ nor $b_q$ breaks the run as $c_p$ because $i>p$, and $i$ is defined to be the first break of the run in $C$.

According to the logic of the merge algorithm, we do not choose the larger one, which means that $a_r\le b_q$. But this contradicts the fact that $a_r=c_p>c_{i+1}=b_q$.

Because we can only arrive at contradictions, the original proposition is true. This means that when we merge to runs, $A$ and $B$, the result tuple (list) $C$ must be a single run.

4.3.2 Number of iterations

The split algorithm ensures that if the original FIFO has $n$ runs, then each output FIFO has about $n∕2$ runs. When $n$ is odd, then one output FIFO has $\left(n∕2\right)+1$ runs.

The merge algorithm, with the proof from the previous section, combines the runs from both input FIFOs into $\left(n∕2\right)+1$ runs when $n$ is odd. If $n$ is even, then the number of runs in the result is $n∕2$/

This means that if we start with 17 runs, there will be at most 9 runs after the first split-merge, at most 5 runs after the second iterations, at most 3 runs after the third, at most 2 runs after the fourth, and sorted after the fifth.

We can think about this backwards. If the result of a split-merge has $n$ runs, then the previous iteration has $2\left(n-1\right)+1$ runs in the worst case. As a result, $k$ split-merge iterations can sort $2^{k-1}+1$ runs.

Want to see the proof of this? Let us define $f\left(1\right)=2$, and $f\left(x\right)=2\left(f\left(x-1\right)-1\right)+1$. Here, the function $f\left(x\right)$ computes the least number of runs given the algorithm completes in $x$ iterations. I claim that $\forall x\ge 1:f\left(x\right)=2^{x-1}+1$. We can prove this by induction. $f\left(1\right)=2^{1-1}+1=2$ is our base case. The induction step states that for all $x\ge 1$, if we assume $f\left(x\right)=2^{x-1}+1$, then

In the worst case that each run is a single value, $k$ split-merge iterations sort $2^{k-1}+1$ values. Because the execution time of each iteration is proportional to the number of values, the execution time of merge sort is proportional to $k\left(2^{k-1}+1\right)$ for an input size of $2^{k-1}+1$.

Instead of expressing everything in $k$, which is the number of iterations needed to sort the input, let us use $N=2^{(}k-1)+1$ instead. We can, then, express the execution time to be proportional to $k\cdot N$. Note that ${log}_2\left(N\right)={log}_2(2^{k-1}+1\approx {log}_2\left(2^{k-1}\right)=k-1$. That means $lo{g}_2\left(N\right)+1\approx k$. As a result, the execution time is proportional to $\left({log}_2\left(N\right)+1\right)N\approx N{log}_2\left(N\right)$.

This means merge sort has a complexity of $O\left(nlog\left(n\right)\right)$. A sorting algorithm cannot have a better complexity! Another module discusses the concept of the big-oh notation.