3.5 bottom up merge_sort

A "bottom up" version of merge sort;

  void merge_sort( sequence A, m, n ) { // solve Merge problem. 
1 for (k = 2; k < n; k = 2*k) {

   
	// Merge chunks of size k/2 into chunks of size k. 
2	for(i = 0, i + k <= n; i = i + k);
3		merge( subseq(A, i+1, i+k), k/2, k );

   
// Now i <= n < i + k.  Must deal with any remaining chunk at the end. 
4    m = n-i; // size of unmerged tail. 
5	if ( k/2 < m ) merge( subseq(A, i, m), k, m );
	}
}

A sketch of the steps of bottom up merging.

0  merge A[i] with A[i+1], for odd i. 
1  merge A[i..i+2-1] with A[i+2..i+4-1], for i = 1 mod 4. 
2  merge A[i..i+4-1] with A[i+4..i+8-1], for i = 1 mod 8. 
3  merge A[i..i+8-1] with A[i+8..i+16-], for i = 1 mod 16. 
... 
k  merge A[i..i+2^k-1] with A[i+2^k..size(A)], for i = 1..