Złożoność czasowa i pamięciowa

Złożoność czasowa:

• Najlepszy przypadek: O(n)
  • Gdy tablica jest już posortowana, sortowanie przez wstawianie wykonuje tylko jedno przejście, aby potwierdzić kolejność sortowania.
• Przypadek średni i najgorszy: O(n²)
  • W przypadku średnim i najgorszym algorytm działa w czasie kwadratowym, ponieważ dla każdego elementu może być konieczne porównanie go z całą posortowaną częścią i przesunięcie jej elementów.

Złożoność pamięciowa:

• O(1)
  • Sortowanie przez wstawianie jest algorytmem „w miejscu”, co oznacza, że nie wymaga dodatkowej pamięci proporcjonalnej do rozmiaru danych wejściowych.
  • Pamięć używana do sortowania pozostaje stała, niezależnie od rozmiaru danych wejściowych.

Podsumowanie:

• Sortowanie przez wstawianie jest wydajne w przypadku małych zbiorów danych lub prawie posortowanych tablic.
• Jest mniej odpowiednie dla dużych zbiorów danych ze względu na kwadratową złożoność czasową.
• Złożoność pamięciowa jest stała, dzięki czemu algorytm jest wydajny pamięciowo dla dowolnego rozmiaru danych wejściowych.