Bad performance of the unsorted list (nearly quadratic time)
For now I'm asking how to optimise deleting of MaxIndex from unsorted list


MaxIndex looks fine. Hard to optimize that further. Maybe you can write a normal for loop that goes from zero to less than the array length so that the JIT can optimize away the range check. You then need to insert if (i &gt;= size) break;. The .NET JIT is not good at optimizing so you have to help. RyuJIT, though, does range checks in loops much, much better.

Your delete is highly inefficient. First of all LINQ is the slowest way to create a new array. Better would be to new it manually and then use Array.Copy to copy over the relevant two sections.

Doing it in-place would be again much faster, at least 2x.

The DeleteAt is probably worse than Array.Copy. It is not very good. It does a lot per item and it does not use memcpy like Array.Copy does. Also, there is no need to create a new array. Just copy in place and do size--.