//  Copyright 2016 The Sawdust Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

package sort;

import static common_lib.Common.mergeInsort;

public class MergeSortNoRecursion {

    /**
     * Merge sort an array without recursion. no thread safe
     * <pre>
     * Idea:
     * 1>   decide the size of sub array from 1, then 2, 4 ,8, 16 .... while the size <= arr.length()
     * 2>   with each size, loop arr from left:
     *   21>     calculate the index of 2 sub arrays: [l, mid] and [mid+1, r]
     *   22>     merge them in sort
     * <a href="http://softwareengineering.stackexchange.com/questions/297160/why-is-mergesort-olog-n">O(NLOGN)</a>
     */
    public static <T extends Comparable<T>> void mergeSortNoRecursion(T[] arr) {
        // Input check
        if (arr == null || arr.length <= 1) { // Note: arr may be empty array: {}
            return;
        }
        Comparable[] helper = new Comparable[arr.length];

        int arrLastIndex = arr.length - 1;
        int subArraySize = 1;
        while (subArraySize <= arr.length) {
            int l = 0;
            int mid = l + subArraySize - 1;
            int rAfterMerge = mid + subArraySize;
            // -> [l, mid] and [mid+1, r]

            while (mid < arrLastIndex) { // adjust when the len is very big or at the end of arr.
                rAfterMerge = rAfterMerge <= arrLastIndex ? rAfterMerge : arrLastIndex;
                mergeInsort(arr, l, mid, rAfterMerge, helper);

                l = rAfterMerge + 1;
                mid = l + subArraySize - 1;
                rAfterMerge = mid + subArraySize;
            }
            subArraySize = subArraySize << 1;
        }
    }
}

@@ -1272,31 +1272,8 @@
 ) %7B%0A
-        // Input check%0A
     
@@ -1316,75 +1316,16 @@
  1) 
-%7B // Note: arr may be empty array: %7B%7D%0A            return;%0A        %7D
+return;%0A
 %0A   
@@ -1342,22 +1342,20 @@
 rable%5B%5D 
-helper
+temp
  = new C
@@ -1380,82 +1380,63 @@
 th%5D;
-%0A%0A        int arrLastIndex = arr.length - 1;%0A        int subArraySize = 1;
+ // space O(N)%0A%0A        int len = 1;%0A        // O(NlgN)
 %0A   
@@ -1451,23 +1451,13 @@
 le (
-subArraySize
+len
  %3C
-=
  arr
@@ -1507,37 +1507,26 @@
    int m
-id
  = l + 
-subArraySize
+len
  - 1;%0A  
@@ -1543,40 +1543,11 @@
 int 
-rAfterMerge = mid + subArraySize
+end
 ;%0A  
@@ -1563,34 +1563,32 @@
  // -%3E %5Bl, m
-id
 %5D and %5Bm
 id+1, r%5D%0A%0A  
@@ -1575,23 +1575,23 @@
 %5D and %5Bm
-id
 +1, 
-r
+end
 %5D%0A%0A     
@@ -1609,173 +1609,121 @@
 e (m
-id
  %3C arr
-LastIndex) %7B // adjust when the len is very big or at the end of arr.%0A                rAfterMerge = rAfterMerge %3C= arrLastIndex ? rAfterMerge : arrLastIndex;
+.length - 1) %7B%0A                end = l + 2 * len - 1;%0A                end = Math.min(end, arr.length - 1);%0A
 %0A   
@@ -1760,31 +1760,19 @@
 l, m
-id, rAfterMerge, helper
+, end, temp
 );%0A%0A
@@ -1795,23 +1795,19 @@
 l = 
-rAfterMerge + 1
+l + 2 * len
 ;%0A  
@@ -1825,29 +1825,18 @@
    m
-id
  = l + 
-subArraySize
+len
  - 1
@@ -1853,99 +1853,32 @@
     
-    rAfterMerge = mid + subArraySize;%0A            %7D%0A            subArraySize = subArraySize
+%7D%0A%0A            len = len
  %3C%3C 

clean merge sort non-recursion