Timsort

**Timsort** on sorteerimisalgoritm, mis on saadud piste- ja ühildusmeetodeid kombineerides ning alusmeetodeid optimeerides ja täiendades. Timsort loodi 2002. aastal Pythoni programmeerimiskeele jaoks Tim Petersi poolt. Lisaks on Timsorti implementeeritud veel mitmed programmeerimiskeeled nagu Java, Swift, ja Rust. Timsort töötab jaga-ja-valitse algoritmi põhimõttel, mis lühidalt seisneb kolmes sammus: jaga sisendmassiiv väiksemateks massiivideks, sorteeri väiksemad massiivid kasutades kahendpistemeetodit, ühilda saadud väiksemad massiivid tagasi üheks tervikuks. Tulemuseks on sorteeritud massiiv. Timsort kasutab ära massiivis juba esinevaid sorteeritud lõike. Timsorti halvima juhu ajaline keerukus on O(*n* log *n*), parima juhu ajaline keerukus aga O(*n*).

## Algoritmi kirjeldus
Timsort on keeruline algoritm. Süvitsi mõistmiseks on kasulik algoritm jagada osadeks. Tim Peters lõi algoritmi põhimõttega, et sorteerides ära kasutada juba sorteeritud lõike, mis esinevad pärismaailmas kasutusel olevatel andmemassiivides. Implementatsiooniks on tarvilik luua kõigepealt meetod kahendotsinguks ning piste- ja ühildusmeetodid. Timsort on stabiilne sorteerimisalgoritm, st sama väärtusega elementide järjekord sorteerimisel ei muutu.

Enne detailsemat algoritmi kirjeldust oleks tarvis teada järgmiseid termineid ja nende põhimõtteid:

* *run* - kui massiivis on üle 64 elemendi, otsib Timsort massiivist natural *run*-e, mis on vähemalt kahest elemendist koosnevad juba sorteeritud massiivi lõigud, mis ongi algoritmi kontekstis run. Kui leitakse kahanevas järjekorras *run*, pööratakse see tagurpidi. Viited nendele lõikudele pannakse pinusse. Väiksematel (pikkus n  |X| + |Y|

ii. |Y| > |X|

Kui üks neist tingimustest on rikutud, ühendatakse omavahel Y ja lühem X või Z seast.

Seda sammu korratakse kuni kogu pinu täidab neid tingimusi.

Käsitlemata *run*-ide puhul vaadeldakse pinu uuesti läbi, tehes vahetusi ja ühildamisi kui vaja.

Kolmanda sammu eesmärk on hiljem ühildusmeetodiga ühendada järjest sarnasema pikkusega *run-*id, et ühildumine oleks efektiivne.

Näide: oletame, et meil on ideaalne juhus, meil on 8 *run*-i suurusega 128, 64, 32, 16, 8, 4, 2, 2 (järjekord on tegelikkuses suvaline). Algoritm ei ühenda ühtegi *run-*i enne, kui 2 ja 2 saavad pinus *run-*e kontrollides kokku. Sellele järgneb 7 perfektset, efektiivset ühendamist.

Neljas samm:

Eelnevas sammus sorteerisime ja ühendasime erinevaid *run-*e, et saada pinusse optimaalne viimane *run-*ide ühendamise järjekord, lähtuvalt pikkustest (et lõplik ühendamine toimuks võimalikult sarnase pikkusega *run-*idest).

Nüüd hakkame järjest ühendama kahe haaval järelejäänud *run-*e, lõpuks saades sorteeritud massiivi.

# loome ajutise *run-*i mille suurus on allesjäänud *run-*idest vähima pikkus
# paneme kõik elemendid lühemast *run*-ist ajutisse *run-*i
# võrdleme suurema ja ajutise *run-*i elemente:

i. neist väiksema asetame lühemasse *run-*i (need elemendid on ajutises olemas)

ii. seame järgmiseks vaadeldavaks elemendiks ära võetud elemendist järgmise

iii. kordame kuni üks *run-*idest (suurem või ajutine) on täielikult läbi vaadatud

Tulemusena lõpuks on sorteeritud massiiv.

Neljandas sammus kasutab algoritm ühildusmeetodit, kuid mitte tavalist - seda on kohandatud, suurendades efektiivsust, kasutamaks eelnevalt leitud *run-*e. See tähendab, et kuigi algoritm justkui ütleb neljandas sammus, et hakkame ükshaaval võrdlema kahe *run-*i elemente, siis tegelikult Timsort teeb seda efektiivsemalt. Näide: olgu meil *run-*id elementidega [1, 2, 3, 4, … 100] ning [101, 102, 103, .. 200]. Ebaefektiivne oleks neid üksikute võrdluste põhjal hakata ühildama.

Timsort kasutab selleks võtet, mida kutsutakse nimega *galloping.* Eesti keeles samuti galopp, tähendab see sisuliselt seda, et elemente ei tõsteta ühildatud, sorteeritud *run-*i mitte ükshaaval, vaid lõikude kaupa, mis kiirendab protsessi, kuna individuaalsete võrdluste arv on vähendatud. Lõigud leitakse kasutades kahendotsingut.

Näide, et toimuvat illustreerida paremini:

Olgu meil *run* X = [1, 2, 3, 4, 5, .. 100] ning Y = [101, 102, 103, .. 200].

Esimesed 7 (eelnevalt defineeritud algne galopi sammu suurus) elementi *run-*ist X võrreldakse *run* Y esimese elemendiga. 101 > 7, 6, 5… Kõik need *run* X elemendid on väiksemad kui mistahes Y elemendid, mistõttu võib kõik need tõsta sorteeritud *run-*i. Vaatluse alla võetakse järgmised *run* X elemendid 8, 9, 10 jne ning võrreldakse taaskord Y esimese elemendi, 101-ga. Galopi samm muutub järjest suuremaks, et leida veel suuremaid lõike, mille saab sorteeritud *run-*i tõsta.

Joonisel on näha, et Y elemendid 9, 12, 13, 14, 15 on kõik väiksemad kui ajutises *run*-is olev element 21, mistõttu võib kõik punaseks värvitud Y elemendid tõsta sorteeritud *run-*i.

Andmete tükkide kaupa liigutamine on märgatavalt kiirem kui elementide ükshaaval võrdlemine ja tõstmine, mis annabki Timsordi tema efektiivsuse ja kiiruse.

## Keerukused
**Ajalised keerukused:**

* Halvim juht: O(*n* log *n*)

* Parim juht: O(*n*)

* Keskmine juht: O(*n* log *n*)

**Ruumiline keerukus:** O(*n*)

## Verifikatsioon
2015. aastal leidsid hollandi ja saksa teadlased tavapärases Java Timsordi implementatsioonis vea ning andsid välja verifitseeritud parandatud algoritmi.

2018. aastal tõestati Timsordi halvima juhu ajaline keerukus.

## Viited