// prvek spojového seznamu
typedef struct prvekSeznamu  {
  // záznam EWD (jen pro ilustraci, že s daty EWD se nehýbe -- v celém programu se jinak nepoužívá)
  EWD zaznam;

  // stáří záznamu (čím starší, tím vyšší číslo)
  int stari;

  // ukazatel na další prvek spojového seznamu (nebo hodnota NULL, pokud je poslední)
  struct prvekSeznamu *dalsi;

} PrvekSeznamu;


// nerekurzivní funkce, která dostane ukazatel na první prvek nesetříděného seznamu
// a vrátí ukazatel na první prvek setříděného seznamu
PrvekSeznamu *EWDSort(PrvekSeznamu *zacatek) {
  if (zacatek == NULL) return NULL; // algoritmus dostal prázdný seznam

  int delkaUseku = 1; // délka slévaných úseků
  int pocetPrvku = 0; // počet prvků spojového seznamu, spočte se v prvním kroku

  PrvekSeznamu *novyZacatek = (PrvekSeznamu *)malloc(sizeof(PrvekSeznamu));
  novyZacatek->dalsi = zacatek;
  PrvekSeznamu *prvek1; // ukazatel na poslední prvek již slité části seznamu
  // při slévání je prvek1 poslední prvek před 1. slévaným úsekem
  PrvekSeznamu *prvek2; // prvek před aktuálně zpracovávaným prvkem
  // prvek2 je poslední prvek před 2. slévaným úsekem

  do { // cyklus dle kroků algoritmu
    prvek1 = novyZacatek; // nastav ukazatele pred začátek
    prvek2 = novyZacatek;


    do { // cyklus slévání dvou úseků
      int delka1 = delkaUseku; // délka prvního slévaného úseku
      int delka2 = delkaUseku; // délka druhého slévaného úseku

      for (int i = 0; i < delkaUseku; i++) { // projdi první úsek
        prvek2 = prvek2->dalsi;
        if (delkaUseku == 1) pocetPrvku++; // v prvním kroku počítáme prvky
        if (prvek2 == NULL) break; // konec seznamu
      }

      if (prvek2 == NULL) break; // druhý úsek je prázdný, nemá cenu slévat

      // dokud nejsou slity všechny prvky v obou úsecích
      while (delka1 > 0 || (delka2 > 0 && prvek2->dalsi != NULL)) {
        // došly prvky v 2. úseku, nebo je 1. prvek 1. úseku starší než 1. prvek 2. úseku
        if (delka2 <= 0 || prvek2->dalsi == NULL
         || (prvek1->dalsi != NULL
             && prvek1->dalsi->stari > prvek2->dalsi->stari)) {
          delka1--;
          prvek1 = prvek1->dalsi; // zatřiďujeme prvek z 1. úseku, stačí tedy posunout ukazatel
        }
        else if (delka1 <= 0) { // došly prvky v 1. úseku
          delka2--;
          prvek1 = prvek1->dalsi; // je třeba posunout oba ukazatele
          prvek2 = prvek2->dalsi;
          if (delkaUseku == 1) pocetPrvku++;
        }
        else { // je třeba přehodit 1. prvek 2. úseku před 1. prvek 1. úseku
          PrvekSeznamu *usek1 = prvek1->dalsi;
          prvek1->dalsi = prvek2->dalsi;
          prvek2->dalsi = prvek2->dalsi->dalsi;
          prvek1->dalsi->dalsi = usek1;
          prvek1 = prvek1->dalsi;
          if (delkaUseku == 1) pocetPrvku++;
          delka2--;
        }
      }

      prvek1 = prvek2;

    } while (prvek2->dalsi != NULL); // dokud nejsme na konci seznamu

    delkaUseku = delkaUseku * 2; // zdvojnásob délku slévaných úseků

  } while (delkaUseku < pocetPrvku); // dokud jsme neslili všechny prvky

  return novyZacatek->dalsi;
}