java - Is there a possible errata in this implementation of bottom up merge sort -

the following code snippet book algorithms robert sedgewick , kevin wayne.

public class mergebu {      // class should not instantiated.     private mergebu() { }      // stably merge a[lo..mid] a[mid+1..hi] using aux[lo..hi]     private static void merge(comparable[] a, comparable[] aux, int lo, int mid, int hi) {          // copy aux[]         (int k = lo; k <= hi; k++) {             aux[k] = a[k];          }          // merge a[]         int = lo, j = mid+1;         (int k = lo; k <= hi; k++) {             if      (i > mid)              a[k] = aux[j++];  // copying unneccessary             else if (j > hi)               a[k] = aux[i++];             else if (less(aux[j], aux[i])) a[k] = aux[j++];             else                           a[k] = aux[i++];         }      }      /**      * rearranges array in ascending order, using natural order.      * @param array sorted      */     public static void sort(comparable[] a) {         int n = a.length;         comparable[] aux = new comparable[n];         (int len = 1; len < n; len *= 2) {             (int lo = 0; lo < n-len; lo += len+len) {                 int mid  = lo+len-1;                 int hi = math.min(lo+len+len-1, n-1);                 merge(a, aux, lo, mid, hi);             }         }         assert issorted(a);     } //other methods } 

my question respect inner loop condition of sort method.

in case input array has 10 elements, pass on array merge subarrays of length 4 leave last 2 elements sorted respect each other not respect other elements.

in next pass, length of subarray merge becomes 8 , still leave last 2 elements unmerged respect other elements. it's last pass array of length 10.

so last 2 elements remain unsorted respect other elements in array because of lo < n-len check. section doesn't @ point number of elements in array should in power of 2. errata or missing something?

i must overlooking because following test code sorts 10 element array correctly.

public static void main(string[] args) {         integer[] array = {1,2,3,4,5,6,7,8,-50, -80};         mergebu.sort(array);         system.out.println(arrays.tostring(array));     } 

can me figure out.

your analysis incorrect. merge proceeds follows.

on pass len = 4, merge 2 subarrays [0-3] , [4-7]. correct last 2 items not merged.

when len = 8, merges 2 subarrays [0-7] , [8-9].

i suspect you're misunderstanding when loop control variable gets incremented. should single-step sort method in debugger, noting values of lo , len in 2 loops.

by way, nothing in definition of merge sort requires length power of two. handling arrays not powers of 2 adds little bit of complexity, though. that's why if (i > mid) , if (j > hi) conditionals in merge loop.