#include<iostream>
    using namespace std;
    struct zivine{
           int sifra;
           char vrsta[40];
           char naziv[40];
           float cijena;
           int dat[3];
    };
    struct Zapis_L{
           zivine vrj;
           Zapis_L *sljedeci;
    };
    typedef Zapis_L *clan;
    typedef Zapis_L lis;
    clan EndL(lis *L){
            return 0;
    }
    clan FirstL(lis *L){
            if(L->sljedeci==NULL) return EndL(L);
            else
            return L->sljedeci;
    }
    lis *InitL(lis *L){
           L=new lis;
           L->sljedeci=NULL;
           return L;}
    clan PreviousL(clan p, lis *L){
            if(p==FirstL(L)) return 0;
            if(p==EndL(L)){
               while(L->sljedeci)
               L=L->sljedeci;
            }
            else{
               while(p!=L->sljedeci)
               L=L->sljedeci;
            }
            return L;
    }
    zivine RetreiveL(clan p, lis *L){
            return p->vrj;}
    int InsertL(zivine x, lis *p, lis *L){
        lis *novi;
        if(p>L->sljedeci || p<0) return 0;
        if(p==EndL(L)){
           while(L->sljedeci)
           L=L->sljedeci;
           novi=new lis;
           L->sljedeci=novi;
           novi->sljedeci=NULL;
           novi->vrj=x;
           return 1;
        }
        else{
         p=PreviousL(p,L);
         novi=new lis;
         novi->sljedeci=L->sljedeci;
         p->sljedeci=novi;
         novi->vrj=x;
         return 1;
         }
    }
    clan NextL(clan p, lis *L){
            if(p->sljedeci==NULL) return EndL(L);
            if(p==EndL(L)) return 0;
            else{
              return p->sljedeci;
            }
    }
    int DeleteL(clan p, lis *L){
        clan prethodni, tekuci;
        tekuci=p;
        if(tekuci==EndL(L))return 0;
        if(p==FirstL(L)){
           L->sljedeci=tekuci->sljedeci;
           delete tekuci;
           return 1;
        }
        else{
           prethodni=PreviousL(tekuci,L);
           prethodni->sljedeci=tekuci->sljedeci;
           delete tekuci;
           return 1;
        }
        return 0;
    }
    clan LocateL(zivine x, lis *L){
            clan pozicija=EndL(L);
            pozicija=PreviousL(pozicija,L);
            if(strlen(x.naziv)>0){
               if(EndL(L)!=FirstL(L)){
                  while(5){
                     zivine tekuci=RetreiveL(pozicija,L);
                     if(strcmp(x.naziv,tekuci.naziv)==0)
                        return pozicija;
                     if(pozicija==FirstL(L))break;
                        pozicija=PreviousL(pozicija,L);
                  }
               }
            }
            if(strlen(x.vrsta)>0){
               if(EndL(L)!=FirstL(L)){
                  while(5){
                     zivine tekuci=RetreiveL(pozicija,L);
                     if(strcmp(x.vrsta,tekuci.vrsta)==0)
                        return pozicija;
                     if(pozicija==FirstL(L))break;
                     pozicija=PreviousL(pozicija,L);
                  }
               }
            }
            return EndL(L);
    }
    clan DeleteAll(lis *L){
            clan tekuci,prijasnji;
            prijasnji=L;
            tekuci=L->sljedeci;
            while(tekuci){
               delete prijasnji;
               prijasnji=tekuci;
               tekuci=tekuci->sljedeci;
            }
            delete prijasnji;
            L=NULL;
            return NULL;
    }
    void Merge(zivine polje[],int i, int k, int j){
         int start=i, zad=k+1, br=0, vel=j-i+1;
         zivine *pom=new zivine[j-i+1];
         while(start<=k && zad<=j){
            if(polje[start].cijena>polje[zad].cijena)
               pom[br++]=polje[start++];
            else if(polje[start].cijena<polje[zad].cijena)
               pom[br++]=polje[zad++];
            if(polje[start].cijena==polje[zad].cijena){
               if(strcmp(polje[start].naziv,polje[zad].naziv)==1)
               pom[br++]=polje[start++];
               else
               pom[br++]=polje[zad++];
            }
         }
         while(start<=k)
            pom[br++]=polje[start++];
         while(zad<=j)
            pom[br++]=polje[zad++];
         for(int I=0;I<vel;I++)
            polje[i+I]=pom[I];
         delete []pom;
     }
    void Zapis(zivine polje[],int i, int j){
         int sred;
         if(i<j){
            sred=(i+j)/2;
            Zapis(polje,i,sred);
            Zapis(polje,sred+1,j);
            Merge(polje,i,sred,j);
         } 
    }
    void Stavi(zivine polje[],int velicina){
        clan sortirana=InitL(sortirana);
        clan novi,zadnji;
        zadnji=sortirana;
        for(int i=0; i<velicina;i++){
           while(zadnji->sljedeci)
              zadnji=zadnji->sljedeci;
           novi=new lis;
           zadnji->sljedeci=novi;
           novi->sljedeci=NULL;
           novi->vrj.sifra=polje[i].sifra;
           strcpy(novi->vrj.naziv,polje[i].naziv);
           novi->vrj.dat[0]=polje[i].dat[0];
           novi->vrj.dat[1]=polje[i].dat[1];
           novi->vrj.dat[2]=polje[i].dat[2];
           strcpy(novi->vrj.vrsta,polje[i].vrsta);
           novi->vrj.cijena=polje[i].cijena;
           cout<<"Sifra: "<<novi->vrj.sifra<<endl;
           cout<<"Naziv: "<<novi->vrj.naziv<<endl;
           cout<<"Cijena: "<<novi->vrj.cijena<<endl;
           cout<<"Vrsta: "<<novi->vrj.vrsta<<endl;
           cout<<"Datum: "<<novi->vrj.dat[0]<<"."<<novi->vrj.dat[1]<<"."<<novi->vrj.dat[2]<<"."<<endl;
           cout<<endl;
        }
    }
    void Merge(lis *L,clan i, clan j){
         if(FirstL(L)!=EndL(L)){
             int velicina=0,br=0;
             clan zadnji;
             zadnji=L;
             while(zadnji->sljedeci){
                zadnji=zadnji->sljedeci;
                velicina++;
             }
             zivine *pom=new zivine[velicina];
             clan mjesto=L->sljedeci;
             while(mjesto){
               pom[br++]=RetreiveL(mjesto,L);
               mjesto=mjesto->sljedeci;
             }
             Zapis(pom,0,velicina-1);
             Stavi(pom,velicina);
         }
         else
         cout<<"Prazna lista! "<<endl;
    }