#include<iostream>
using namespace std;
typedef int element;
struct zivotinja{
    int sifra;
    char vrsta[35];
    char naziv[35];
    float cijena;
    int datum[3];        
};
struct Lista_zapis{
       zivotinja vrijednost[1000];
       int kursor;                
};
typedef struct Lista_zapis lista;
element EndL(lista *L){
    return (L->kursor);
}
element FirstL(lista *L){
          if(L->kursor==0) 
                          return EndL(L); 
           else 
                return 0;      
}
zivotinja RetreiveL(element p, lista *L){
        return L->vrijednost[p];
}
element InsertL(zivotinja x,element p,lista *L){
          if(p>L->kursor || p<0) return 0;
              else{
                 for( int q=L->kursor;q>=p;q--)
                      L->vrijednost[q+1]=L->vrijednost[q];
                 L->kursor++;
                 L->vrijednost[p]=x;
                 return 1;  }  
}
lista *InitL(lista *L){
      L=new lista;
      L->kursor=0;
      return L;
}
element NextL(element p, lista *L){
        if(p==EndL(L)-1) return EndL(L);
        if(p==EndL(L)) return 0;
        else 
             return p+1;
}
element PreviousL(element p, lista *L){
        if(p==FirstL(L)) return -1;
        if(p==EndL(L)) return p-1;
        return p-1;       
}
element DeleteL(element p, lista *L){
    if((L->kursor==0))
         return 0;
     if((p>=L->kursor)||(p<0))
         return 0;
       if(p==EndL(L))
                      return 0;   
       if(p==FirstL(L)){
          L->kursor--;
         for( int i=p; i<L->kursor; i++)
              L->vrijednost[i]=L->vrijednost[i+1];
         return 1;
                        }
    else{
         L->kursor--;
         for( int i=p; i<L->kursor; i++)
              L->vrijednost[i]=L->vrijednost[i+1];
         }
     return 1;    
}
element DeleteAll(lista *L){
        return L->kursor==0;       
}
element LocateL(zivotinja x, lista *L){
        element pozicija=EndL(L);
        pozicija=PreviousL(pozicija,L);
        if(strlen(x.naziv)>0){
        if(FirstL(L)!=EndL(L)){
        while(5){
                 zivotinja sad=RetreiveL(pozicija,L);
                 if(strcmp(x.naziv,sad.naziv)==0)
                                            return pozicija;
                 if(pozicija==FirstL(L))break;
                 pozicija=PreviousL(pozicija,L);
                 }
                 }}
        if(strlen(x.vrsta)>0){
        if(FirstL(L)!=EndL(L)){
        while(5){
                 zivotinja sad=RetreiveL(pozicija,L);
                 if(strcmp(x.vrsta,sad.vrsta)==0)
                                            return pozicija;
                 if(pozicija==FirstL(L))break;
                 pozicija=PreviousL(pozicija,L);
                 }
                 }}
        return EndL(L);
}
void Merge(lista *L,int i,int k,int j){
     int beg=i, sec=k+1, br=0, vel=j-i+1;
     zivotinja *pomocno = new zivotinja [j-i+1];
     while (beg<=k && sec<=j){
           if(L->vrijednost[beg].cijena>L->vrijednost[sec].cijena)
                 pomocno[br++]=L->vrijednost[beg++];
           else if(L->vrijednost[beg].cijena<L->vrijednost[sec].cijena)
               pomocno[br++]=L->vrijednost[sec++];
           if(L->vrijednost[beg].cijena==L->vrijednost[sec].cijena){
            if(strcmp(L->vrijednost[beg].naziv,L->vrijednost[sec].naziv)==1)
                      pomocno[br++]=L->vrijednost[beg++];  
            else
               pomocno[br++]=L->vrijednost[sec++];                                                         
           }
           }
 
    while(beg<=k)
            pomocno[br++]=L->vrijednost[beg++];
   while(sec<=j) 
                 pomocno[br++]=L->vrijednost[sec++];                   
   for(int I=0;I<vel;I++)
           L->vrijednost[i+I]=pomocno[I];
   delete []pomocno;
}
 
 
void Sort(lista *L, int i,int j){
    int middle; 
    if(i<j){
           middle=(i+j)/2; 
           Sort(L,i,middle);
           Sort(L,middle+1,j);
           Merge(L,i,middle,j);
           }
 
}
void MSort(lista *L,int i,int j){    
     if(FirstL(L)==EndL(L)){
                            cout<<"Lista je prazna "<<endl;
                            return;
                            }                
     Sort(L,0,EndL(L)-1);
      zivotinja sad;
      for(int i=0;i<=EndL(L)-1;i++){
               sad=L->vrijednost[i];      
                cout<<"Sifra "<<sad.sifra<<endl;              
                cout<<"Naziv "<<sad.naziv<<endl; 
                cout<<"Datum "<<sad.datum[0]<<"."<<sad.datum[1]<<"."<<sad.datum[2]<<endl;
                cout<<"Vrsta "<<sad.vrsta<<endl;
                cout<<"Cijena "<<sad.cijena<<endl;
                cout<<endl; }
}