public static void TestFindKth()
    {
        System.out.println("Starting Testing FindKth ..");
        // generate random arrays and sort them, loop many times
        // int[] array = {2,2,9,0};
        // int k = 2;
        // for (Integer aa : array) {
        //     System.out.printf("%d ", aa);
        // }
        // System.out.println();

        // int[] a1 = array.clone();
        // int[] a2 = array.clone();

        // // sort arrays
        // Arrays.sort(a1);
        // int result = Sort.findkth(a2, k);
        // System.out.println("k = " + k);
        // System.out.println("output: " + result);
        // System.out.println("expected: " + a1[k - 1]);
        for (int i = 0; i < 3000; i++)
        {
            int size = (int) (Math.random() * 3000) + 1;

            // generate a random array
            int[] array = new int[size];
            int k = (int) (Math.random() * size) + 1;
            for (int j = 0; j < size; j++) {
                array[j] = (int) (Math.random() * 3000);
            }
            // for (Integer aa : array) {
            //     System.out.printf("%d ", aa);
            // }
            // System.out.println();

            int[] a1 = array.clone();
            int[] a2 = array.clone();

            // sort arrays
            Arrays.sort(a1);
            int result = Sort.findkth(a2, k);
            // System.out.println("k = " + k);
            // System.out.println("output: " + result);
            // System.out.println("expected: " + a1[k - 1]);

            if (result != a1[k - 1]) {
                System.out.println("*** Error ***");
                return;
            }
        }
        System.out.println("Passed ^_^");
    }