ühinemissorteerimine

Ühine missorteerimine on sorteerimisalgoritm, mis jagab sisendjärjestuse kahte alamjärjestusse ja rakendab seejärel rekursiivselt ennast neile alamjärjestustele. Pärast alamjärjestuste sorteerimist ühendab ta need uuesti üheks sorteeritud järjestuseks. Ühine missorteerimine kasutab jaotamise ja vallutamise strateegiat. Selle keskmine ja halvimal juhul ajaline keerukus on O(n log n), kus n on sisendjärjestuse elementide arv. Ruumi keerukus on O(n) või O(log n) sõltuvalt rakenduse tüübist. Ühine missorteerimine on stabiilne algoritm, mis tähendab, et see säilitab võrdsete elementide suhtelise järjekorra. Selle stabiilsus muudab selle kasulikuks mitmesugustes rakendustes, kus järjekorra säilitamine on oluline. Ühine missorteerimine on laialt levinud oma tõhususe ja prognoositava jõudluse tõttu. Seda kasutatakse sageli teiste algoritmide alusena või osana keerukamatest süsteemidest.