Úloha 5.2

#include <iostream>
#include <list>
#include <string>
#include <cstring>    // pre std::strcmp

using namespace std;

/**
 * Zoradí zreťazený zoznam reťazcov pomocou algoritmu Merge Sort.
 *
 * @param lst        Zreťazený zoznam (std::list<std::string>&).
 *                   Po volaní bude obsahovať zotriedené prvky.
 * @param ascending  True = vzostupne (lexikograficky od "a" po "z"),
 *                   False = zostupne.
 */
void mergeSort(list<string> &lst, bool ascending = true) {
    // Základný prípad: triválne zotriedenie pre 0 alebo 1 prvok
    if (lst.size() <= 1) return;

    // 1) Rozdelíme zoznam na dve polovice
    list<string> left, right;
    auto it = lst.begin();
    std::advance(it, lst.size() / 2);  // posunieme iterátor na stred
    // prvú polovicu [begin, it) presunieme do left
    left.splice(left.begin(), lst, lst.begin(), it);
    // zostávajúcu druhú polovicu presunieme do right
    right.splice(right.begin(), lst, lst.begin(), lst.end());
    // lst je teraz prázdny

    // 2) Rekurzívne zotriedime obe polovice
    mergeSort(left, ascending);
    mergeSort(right, ascending);

    // 3) Zlúčime obidva zotriedené zoznamy späť do lst
    auto cmp = [&](const string &a, const string &b) {
        int r = std::strcmp(a.c_str(), b.c_str());
        return ascending ? (r <= 0)   // pre vzostupne: a <= b
                         : (r > 0);   // pre zostupne: a >  b
    };

    // iteratívne porovnávame fronty left a right
    while (!left.empty() && !right.empty()) {
        if (cmp(left.front(), right.front())) {
            // zoznam lst doplníme prvým prvkom z left
            lst.splice(lst.end(), left, left.begin());
        } else {
            lst.splice(lst.end(), right, right.begin());
        }
    }
    // zvyšné prvky (jedného zo zoznamov) presunieme na koniec
    if (!left.empty())
        lst.splice(lst.end(), left);
    if (!right.empty())
        lst.splice(lst.end(), right);
}

/** Pomocná funkcia na výpis obsahu list<string> */
void printList(const list<string> &lst) {
    cout << "[ ";
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        cout << '"' << *it << "\" ";
    }
    cout << "]\n";
}

int main() {
    // Príklad 1: vzostupné zotriedenie
    list<string> l1 = { "Milan", "Martin", "Eva" };
    cout << "Povodny zoznam: ";
    printList(l1);
    mergeSort(l1, true);
    cout << "Zoradene vzostupne: ";
    printList(l1);
    // Očakávaný výstup: ["Eva", "Martin", "Milan"]

    // Príklad 2: vzostupne s prazdnym retazcom
    list<string> l2 = { "Fero", "Jano", "" };
    cout << "\nPovodny zoznam: ";
    printList(l2);
    mergeSort(l2, true);
    cout << "Zoradene vzostupne: ";
    printList(l2);
    // Očakávaný výstup: ["", "Fero", "Jano"]

    // Príklad 3: zostupne zotriedenie
    list<string> l3 = { "Apple", "Banana", "Cherry" };
    cout << "\nPovodny zoznam: ";
    printList(l3);
    mergeSort(l3, false);
    cout << "Zoradene zostupne: ";
    printList(l3);
    // Očakávaný výstup: ["Cherry", "Banana", "Apple"]

    return 0;
}