Iterative / non-recursive merge sort

Question

I tried to sort the iterative merge, but got stuck in conditions where the input length is not 2 ^ x.

as int [] A = {4,5,1,254,66,75,12,8,65,4,87,63,53,8,99,54,12,34};

public class MergeSort { public static void sort(int[] A) { System.out.println("Log(A.len):"+log(A.length, 2)); for (int i = 0; i < log(A.length, 2); i++) { //log A.len int r = 2 << i; //2^i int mid = r >>> 1; for (int j = 0; j+r < A.length; j = j + r) { System.out.print("offset:" + j + " mid:" + (j + mid) + " r:" + (j + r)); merge(A, j, (j + mid), (j + r)); } } } public static void merge(int[] A, int offset, int mid, int n) { mid = mid - offset; n = n - offset; int[] L = new int[mid]; int[] R = new int[n - mid]; for (int i = 0; i < mid; i++) { L[i] = A[i + offset]; R[i] = A[mid + i + offset]; } System.out.print("\nL:"); print_array(L); System.out.print("\nR:"); print_array(R); int l = 0; int r = 0; //left right pointer int k = offset; while (l < mid && r < mid) { if (L[l] < R[r]) { // System.out.println("in left"); A[k] = L[l]; l++; } else { // System.out.println("in right"); A[k] = R[r]; r++; } k++; } while (l < mid) { A[k] = L[l]; l++; k++; } while (r < mid) { A[k] = R[r]; r++; k++; } System.out.print("\nA:"); print_array(A); System.out.print("\n\n"); } public static void main(String[] args) { int[] A ={4,5,1,254,66,75,12,8,65,4,87,63,53,8,99,54,12,34}; sort(A); } public static void print_array(int[] A) { for (int i = 0; i < A.length; i++) { System.out.print(A[i] + " "); } } static int log(int x, int base) { return (int) (Math.log(x) / Math.log(base)); } } 

It works great when the input length is 2 ^ x.

There is also a better way to implement an iterative version, it looks very dirty.

Answer 1

C ++ example merge sorting from bottom to top. a [] is an array to sort, b [] is a temp array. It includes checking the number of merge passes and swaps in place, if the number of passes is odd, in order to eventually receive the sorted data in [].

 void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee); void BottomUpCopy(int a[], int b[], size_t ll, size_t rr); size_t GetPassCount(size_t n); void BottomUpMergeSort(int a[], int b[], size_t n) { size_t s = 1; // run size if(GetPassCount(n) & 1){ // if odd number of passes for(s = 1; s < n; s += 2) // swap in place for 1st pass if(a[s] < a[s-1]) std::swap(a[s], a[s-1]); s = 2; } while(s < n){ // while not done size_t ee = 0; // reset end index while(ee < n){ // merge pairs of runs size_t ll = ee; // ll = start of left run size_t rr = ll+s; // rr = start of right run if(rr >= n){ // if only left run rr = n; BottomUpCopy(a, b, ll, rr); // copy left run break; // end of pass } ee = rr+s; // ee = end of right run if(ee > n) ee = n; BottomUpMerge(a, b, ll, rr, ee); } std::swap(a, b); // swap a and b s <<= 1; // double the run size } } void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee) { size_t o = ll; // b[] index size_t l = ll; // a[] left index size_t r = rr; // a[] right index while(1){ // merge data if(a[l] <= a[r]){ // if a[l] <= a[r] b[o++] = a[l++]; // copy a[l] if(l < rr) // if not end of left run continue; // continue (back to while) do // else copy rest of right run b[o++] = a[r++]; while(r < ee); break; // and return } else { // else a[l] > a[r] b[o++] = a[r++]; // copy a[r] if(r < ee) // if not end of right run continue; // continue (back to while) do // else copy rest of left run b[o++] = a[l++]; while(l < rr); break; // and return } } } void BottomUpCopy(int a[], int b[], size_t ll, size_t rr) { do // copy left run b[ll] = a[ll]; while(++ll < rr); } size_t GetPassCount(size_t n) // return # passes { size_t i = 0; for(size_t s = 1; s < n; s <<= 1) i += 1; return(i); }