Przeczytałem, że operacja wstawiania w zestawie zajmuje tylko czas log (n). Jak to możliwe?

Aby wstawić, najpierw znajdujemy lokalizację w posortowanej tablicy, w której musi znajdować się nowy element. Przy użyciu wyszukiwania binarnego pobiera log (n). Następnie, aby wstawić w tym miejscu, wszystkie elementy, które mu się powiodą, należy przesunąć o jedno miejsce w prawo. To zajmuje kolejny czas.

Moje wątpliwości opierają się na moim zrozumieniu, że zbiór jest zaimplementowany jako tablica, a elementy są przechowywane w posortowanej kolejności. Popraw mnie, jeśli moje zrozumienie jest błędne.