Тази статия не казва ли точно че BigList<T> трябва да е по-бърз от List<T> за всякакво инсъртване различно от инсърътване в края, за големи колекции.В случая аз инсъртвам по средата, което при List<T> би трябвало да има сложност n/2, а при BigList<T> сложността би трябвало да е logN тъй като BigList<T> е въже, но пърформанс тестовете ми не показват това.

От същата статия: 

 using an index to get or change one element of a BigList, while still reasonably efficient, is significantly slower than using a plain List

Insert метода, който ползваш в тестовете си използва точно индекс и най-вероятно от там идва забавянето.

Не мисля че е така, защото аз не ползвам индекс за да взема някакъв елемент от листа. Аз ползвам индекс за да кажа къде точно в листа искам да ми се инсъртне елемента, което би трябвало да работи по-бързо от обикновения лист.

От статията:

With List<T>, inserting or removing elements from anywhere in a large list except the end is very inefficient -- every item after the point of inserting or deletion has to be moved in the list. The BigList<T> class, however, allows for fast insertions and deletions anywhere in the list.

Индекса, който подаваш като параметър за инсърта не е достъпен директно, а трябва да се итерира до елемента преди него, което е бавна операция.

EDIT:

Нямам възможност да правя тестове в момента, но очаквам инсърт в началото на BigList-а да е доста по-бърз от инсърт в средата (което при до 2 мил. елемента стига до индекс 1 мил.), защото мястото на инсърта ще бъде достигнато по-бързо, а самият инсърт е на практика "безплатен".

Еми доколкото знам BigList не е свързан списак, а въже, което означава, че намирането на индекса би трябвало да отнема O(log N) операции, което би трябвало да е по-бързо от листа, който за да инсъртне на позиция 1 мил. при 2 мил. елемента трябва да премести 1 мил. елемента с една позиция напред. Във самата статия е казано, че добавянето е бързо навсякъде в BigList, а не само в началото или в края:

 The BigList<T> class, however, allows for fast insertions and deletions anywhere in the list.

Да, изказах се неподготвен по-горе :)

BigList-a действително не е свързан списък и по-горните ми предположения не са верни.

Прегледах му набързо Source кода и новото ми предположение е, че се бави заради често ребалансиране на дървото при толкова интензивни инсърти на последователни числа.

Да точно така е. Благодаря много. Тук тествам с инсърт на рандом позиция https://pastebin.com/XAbZE40z и в действителност BigList е по-бърз, както се очаква.