Kicksort_sort

/* Programmer     : Dhruv Patel
*  Problem Name   : Tidy Numbers
*  Used In        : Google
*  Used As        : Kicksort
*  Problem        :
*                
*                   Here at Kickstart, we are fans of the well-known Quicksort algorithm, which chooses a pivot value from a list, 
*                   moves each other value into one of two new lists depending on how it compares with the pivot value, and then 
*                   recursively sorts each of those new lists. However, the algorithm might choose a pivot that causes all of the 
*                   other values to end up in only one of the two new lists, which defeats the purpose of the divide-and-conquer 
*                   strategy. We call such a pivot a worst-case pivot.
*                   To try to avoid this problem, we have created our own variant, Kicksort. Someone told us that it is good to use 
*                   a value in the middle as a pivot, so our algorithm works as follows:
*                   Kicksort(A): // A is a 0-indexed array with E elements
*                     If E ≤ 1, return A.
*                   Otherwise:
*                     Create empty new lists B and C.
*                     Choose A[floor((E-1)/2)] as the pivot P.
*                     For i = 0 to E-1, except for i = floor((E-1)/2):
*                   If A[i] ≤ P, append it to B.
*                   Otherwise, append it to C.
*                   Return the list Kicksort(B) + P + Kicksort(C).
*                   For practice, we are trying Kicksort out on lists that are permutations of the numbers 1 through N. 
*                   Unfortunately, it looks like Kicksort still has the same problem as Quicksort: it is possible for every pivot 
*                   to be a worst-case pivot!
*                   For example, consider the list 1 4 3 2. Kicksort will choose 4 as a pivot, and all of the other values 1 3 2 
*                   will end up in one of the two new lists. Then, when Kicksort is called on that list 1 3 2, it will choose 3, 
*                   and once again, all of the other values will end up in one of the two new lists. Finally, it will choose 1 from 
*                   the list 1 2, and the other value 2 will of course end up in only one of the two new lists. In every case, the 
*                   algorithm will choose a worst-case pivot. (Notice that when Kicksort is called on a list with 0 or 1 elements, 
*                   it does not choose a pivot at all.)
*  Given a permutation of the numbers 1 through N, determine whether Kicksort will choose only worst-case pivots.
*
*  Input           :
*                   The first line of the input gives the number of test cases, T. T test cases follow; each consists of two lines. 
*                   The first line has one integer N: the number of elements in the permutation. The second line contains N integers Ai,
*                   which are a permutation of the values from 1 through N.
*
*  Output          :
*                   For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and 
*                   y is YES if Kicksort will choose only worst-case pivots when sorting this list, or NO otherwise.
*  Limits
*                   The values Ai are a permutation of the values from 1 to N.
*                   
*                   Small dataset
*
*                   1 ≤ T ≤ 32.
*                   2 ≤ N ≤ 4.
*
*                   Large dataset
*                   1 ≤ T ≤ 100.
*                   2 ≤ N ≤ 10000.
*  Input                                                              Output
*                   4
*                   4                                                 
*                   1 4 3 2                                           Case #1: 1,2,3,4
*                   4
*                   2 1 3 4                                           Case #2: 1,2,3,4
*                   2
*                   2 1                                               Case #3: 1,2
*                   3
*                   1 2 3                                             Case #4: 1,2,3
*
*  Thoughts       =>
*                   It's a modified version of quicksort algorithm in which we create pivot in the middle.
*                   There are nothing specific rules to avoid selecting worst case pivot.We simply select
*                   the middle one in order to optmize the worst case pivot selection.
*/
import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static Instant start;
    static boolean flag = false;
    public static void Kicksort(List<Integer> a) {
        boolean sorted = true;
        for(int i=0; i < a.size(); i++){                                          // Bubble-sort to select the list is sorted or not.
            for(int j=1; j < (a.size()-i); j++){                                  
                if(a.get(j-1) > a.get(j)){
                    sorted = false;                                               // We are slightly optimizing the worst case.
                    break;
                }
            }
        }
        int elements = a.size();
        List<Integer> b = new ArrayList<>();
        List<Integer> c = new ArrayList<>();
        int pivot = 0;
        if(elements <=1){
            return;
        }
        pivot = a.get(Math.floorDiv(elements-1,2));
        for(int i = 0 ; i <= elements-1;i++){
            if(Math.floorDiv(elements-1,2)!=i){
                if(a.get(i) <= pivot){
                    b.add(a.get(i));
                }else{
                    c.add(a.get(i));
                }
            }
        }

        if(b.isEmpty() || c.isEmpty()){
            flag = true;
        }else{
            flag = false;
        }
        List<Integer> p = new ArrayList<>();
        p.addAll(b);
        p.add(pivot);
        p.addAll(c);
        if(!sorted){
            Kicksort(p);
        }else{
            Instant end = Instant.now();
            System.out.println("Sorted Numbers are: "+p.toString()+" "+ Duration.between(end,start).toNanos());
            return;
        }

    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        int i = 1;
        while (--T >= 0) {
            flag = false;
            input.nextLine();
            int N = input.nextInt();
            List<Integer> list = new ArrayList<>();
            input.nextLine();
            while(--N>=0){
                list.add(input.nextInt());
            }
            System.out.println("Numbers are = " + list.toString());
            start = Instant.now();
            Kicksort(list);
            //String answer = "";
            //if(flag){answer="YES";}else{answer="NO";}
            //System.out.println("Case #"+i+": "+answer);
            i++;
        }
    }
}