// Path: src/org/burstsort4j/LazyFunnelsort.java
// static interface Kmerger {
// 
//     /**
//      * Merges k^3 elements from the inputs and writes them to the output.
//      */
//     void merge();
// }
// 
// Path: src/org/burstsort4j/LazyFunnelsort.java
// static class MergerFactory {
// 
//     private MergerFactory() {
//     }
// 
//     /**
//      * Creates a new instance of Kmerger to merge the input buffers.
//      *
//      * @param  inputs  streams of sorted input to be merged.
//      * @param  offset  first element in list to be merged.
//      * @param  count   number of elements in list to be merged, starting
//      *                 from the {@code offset} position.
//      * @param  output  buffer to which merged results are written.
//      * @return  a Kmerger instance.
//      */
//     @SuppressWarnings("unchecked")
//     public static Kmerger createMerger(
//             List<CircularBuffer<Comparable>> inputs, int offset,
//             int count, CircularBuffer<Comparable> output) {
//         // Tests indicate the values of 8 and 16 do not help performance.
//         if (count > 4) {
//             return new BufferMerger(inputs, offset, count, output);
//         } else {
//             // Convert the sublist to an array for insertion merger.
//             CircularBuffer[] buffers = new CircularBuffer[count];
//             ListIterator<CircularBuffer<Comparable>> li =
//                     inputs.listIterator(offset);
//             for (int ii = 0; ii < count; ii++) {
//                 buffers[ii] = li.next();
//             }
//             return new InsertionMerger(buffers, output);
//         }
//     }
// }


import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import org.burstsort4j.LazyFunnelsort.Kmerger;
import org.burstsort4j.LazyFunnelsort.MergerFactory;
import org.junit.Test;
import static org.junit.Assert.*;
        test_Mergers(data, 4);
        test_Mergers(data, 8);
        test_Mergers(data, 16);
        test_Mergers(data, 32);
        test_Mergers(data, 64);
    }

    /**
     * Tests the merger implementations for correctness using the given
     * data. This only tests the case where the inputs are circular buffers.
     *
     * @param  data        data to use for testing (will not be modified).
     * @param  partitions  number of partitions to create, sort and merge
     */
    private void test_Mergers(List<String> data, int partitions) {
        String[] arr = data.toArray(new String[data.size()]);
        // Split up the inputs for the insertion d-way merger.
        List<CircularBuffer<Comparable>> inputs = new ArrayList<CircularBuffer<Comparable>>();
        int size = arr.length / partitions;
        int offset = 0;
        while (offset < arr.length) {
            if (offset + size > arr.length) {
                size = arr.length - offset;
            }
            Arrays.sort(arr, offset, offset + size);
            inputs.add(new CircularBuffer<Comparable>(arr, offset, size, false));
            offset += size;
        }
        CircularBuffer<Comparable> output = new CircularBuffer<Comparable>(arr.length);
        // Test the merger.
// Path: src/org/burstsort4j/LazyFunnelsort.java
// static interface Kmerger {
// 
//     /**
//      * Merges k^3 elements from the inputs and writes them to the output.
//      */
//     void merge();
// }
// 
// Path: src/org/burstsort4j/LazyFunnelsort.java
// static class MergerFactory {
// 
//     private MergerFactory() {
//     }
// 
//     /**
//      * Creates a new instance of Kmerger to merge the input buffers.
//      *
//      * @param  inputs  streams of sorted input to be merged.
//      * @param  offset  first element in list to be merged.
//      * @param  count   number of elements in list to be merged, starting
//      *                 from the {@code offset} position.
//      * @param  output  buffer to which merged results are written.
//      * @return  a Kmerger instance.
//      */
//     @SuppressWarnings("unchecked")
//     public static Kmerger createMerger(
//             List<CircularBuffer<Comparable>> inputs, int offset,
//             int count, CircularBuffer<Comparable> output) {
//         // Tests indicate the values of 8 and 16 do not help performance.
//         if (count > 4) {
//             return new BufferMerger(inputs, offset, count, output);
//         } else {
//             // Convert the sublist to an array for insertion merger.
//             CircularBuffer[] buffers = new CircularBuffer[count];
//             ListIterator<CircularBuffer<Comparable>> li =
//                     inputs.listIterator(offset);
//             for (int ii = 0; ii < count; ii++) {
//                 buffers[ii] = li.next();
//             }
//             return new InsertionMerger(buffers, output);
//         }
//     }
// }


// Path: test/org/burstsort4j/LazyFunnelsortTest.java
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import org.burstsort4j.LazyFunnelsort.Kmerger;
import org.burstsort4j.LazyFunnelsort.MergerFactory;
import org.junit.Test;
import static org.junit.Assert.*;

        test_Mergers(data, 4);
        test_Mergers(data, 8);
        test_Mergers(data, 16);
        test_Mergers(data, 32);
        test_Mergers(data, 64);
    }

    /**
     * Tests the merger implementations for correctness using the given
     * data. This only tests the case where the inputs are circular buffers.
     *
     * @param  data        data to use for testing (will not be modified).
     * @param  partitions  number of partitions to create, sort and merge
     */
    private void test_Mergers(List<String> data, int partitions) {
        String[] arr = data.toArray(new String[data.size()]);
        // Split up the inputs for the insertion d-way merger.
        List<CircularBuffer<Comparable>> inputs = new ArrayList<CircularBuffer<Comparable>>();
        int size = arr.length / partitions;
        int offset = 0;
        while (offset < arr.length) {
            if (offset + size > arr.length) {
                size = arr.length - offset;
            }
            Arrays.sort(arr, offset, offset + size);
            inputs.add(new CircularBuffer<Comparable>(arr, offset, size, false));
            offset += size;
        }
        CircularBuffer<Comparable> output = new CircularBuffer<Comparable>(arr.length);
        // Test the merger.
        Kmerger merger = MergerFactory.createMerger(inputs, 0, inputs.size(), output);