เวลาในการเรียงลำดับอาเรย์จะเปลี่ยนแปลงอย่างมากใน Java ตามขนาด Gap ได้อย่างไร

โดยทั่วไปฉันสร้างอาร์เรย์สุ่ม 10 อาร์เรย์จากขนาด: 8000,16000,32000,64000,128000,256000

สิ่งที่ฉันหมายถึงคือฉันมี 10 อาร์เรย์ขนาด 8000, 10 อาร์เรย์ขนาด 16000 ฯลฯ

ทั้งหมดนี้เต็มไปด้วยตัวเลขสุ่มตั้งแต่ 0 ถึงขนาดอาร์เรย์

ฉันมีการใช้งานสำหรับการเรียงลำดับเชลล์:

public static void sortMyArray(int[] a){
for (int gap = a.length / 2; gap > 0; gap = (gap / 2)) {
    for (int i = gap; i < a.length; i++) {
        int tmp = a[i];
        int j = i;
        for (; j >= gap && tmp < (a[j - gap]); j -= gap) {
            a[j] = a[j - gap];
        }
        a[j] = tmp;
     }
}
}

เมื่อช่องว่างคือ gap = a.length / a ความยาว ฉันแค่มีการเรียงลำดับการแทรก ต่อไปนี้เป็นเวลาในการจัดเรียงอาร์เรย์เหล่านี้:

Number of Elements  Milliseconds
8000                13
16000               53
32000               217
64000               828
128000              3311
256000              13352

นี่ก็คือประมาณ O(N^2) เมื่อจำนวนองค์ประกอบเพิ่มขึ้นเป็นสองเท่า เวลาในการแก้ไขจะเพิ่มขึ้นเกือบ 4 เท่า

อย่างไรก็ตาม เมื่อฉันใช้ gap = a.length / 2 ฉันได้รับค่าเช่น:

Number of Elements  Milliseconds
8000                2
16000               2
32000               4
64000               10
128000              25
256000              60

นี่ยังดีกว่า O(N) เหรอ? สิ่งนี้เป็นไปได้อย่างไร? ฉันพยายามปิดโปรเซสเซอร์จาก Windows และลองใช้คอมพิวเตอร์โดยใช้โปรเซสเซอร์เพียง 1 ตัวเท่านั้น แต่ค่าต่างๆ ยังคงไม่สมเหตุสมผล

นี่คือรหัสเต็มของฉันหากคุณสนใจ:

int[] arraySizes = new int[]{8000,16000,32000,64000,128000,256000};
Random rn = new Random(1);

for(int i=0;i<arraySizes.length;i++){
    int[] arrayToBeSorted = new int[arraySizes[i]];
    System.out.println("Solving array with: " + arraySizes[i] + " elements with first sorting algorithm.");
    for (int c = 0; c < 10; c++) {
        for(int t=0;t<arraySizes[i];t++){
            int randomNumber = rn.nextInt(arrayToBeSorted.length);
            arrayToBeSorted[t] = randomNumber;
        }
        Long initialTime = (new Date().getTime());
        sortMyArray(arrayToBeSorted);
        Long finalTime = (new Date().getTime());
        System.out.println("Time in milliseconds:" + (finalTime - initialTime));
    }
}