struct datum {
       int dan, godina, mjesec;
       };
struct podaci {
       int sifra;
       char vrsta[40],naziv[40];
       float cijena; 
       datum dat_dost;
       };
struct tlista {
       podaci zivotinja [5000];
       tlista *sljedeci;
       };
 
 
tlista *lista=new tlista;
int sifra=1, br=0;
 
int firstl (tlista *lista) {
    return lista;   
}
 
 
void insertl(podaci x, int br, tlista *lista){
     tlista *zadnji=lista;
     while(zadnji->sljedeci) zadnji=zadnji->sljedeci;
     tlista *novi=new tlista;
     zadnji->sljedeci=novi;
     novi->zivotinja=x;
     novi->sljedeci=NULL;
     }
 
 
 
int endl(tlista  *lista){
    return 0 ;
    }
 
int nextl (int *p, tlista *lista){
    tlista *zadnji= lista;
    while (zadnji->sljedeci) zadnji=zadnji->sljedeci;
    if (!p==zadnji) return p->sljedeci;
    else return 0;
    }
 
tlista locatel (char mat[], tlista *lista){
    tlista *tekuci=lista;
    while(tekuci){
                  if(strcmp(tekuci->zivotinja.naziv,mat)==0) return(int)tekuci;
                  tekuci=tekuci->sljedeci;
                  }
                  return NULL;
    }
 
void initl (tlista *lista){
     lista=NULL;
     }
 
void deletel(tlista *p, tlista *lista){
     tlista *tekuci=p->sljedeci;
     p->sljedeci=tekuci->sljedeci;
     delete tekuci;
     }
podaci retrieveL (int p, tlista *lista){
       tlista *tekuci= lista->sljedeci;
       for(int i=0;i<p;i++) tekuci=tekuci->sljedeci;
       return tekuci->zivotinja;
       }
void deleteallL (tlista *lista) {
     while(lista->sljedeci){
                            tlista *tekuci=lista->sljedeci;
                            lista->sljedeci=tekuci->sljedeci;
                            delete tekuci;
                            }   delete lista;
}
void spoji(podaci a[], int i, int k, int j) {
     int I=i,J=k+1,K=0;
     podaci *b = new podaci [j-i+1];
 
     while(I<=k && J<=j){
 
                if(a[I].cijena>a[J].cijena) b[K++]=a[I++];
                else if(a[I].cijena<a[J].cijena) b[K++]=a[J++];
                else if(strcmp(a[I].naziv,a[J].naziv)==-1) b[K++]=a[J++]; 
                else b[K++]=a[I++];                                              
                }
 
     if(I>k) while(J<=j) b[K++]=a[J++];
     else while(I<=k) b[K++]=a[I++];
 
     for(I=0;I<=j-i;I++) a[i+I]=b[I];
     delete [] b;
 
     }
 
void msort(podaci a[],int i, int j) {
     if(i<j) {
             int k=(i+j)/2;
             msort(a,i,k);
             msort(a,k+1,j);
             spoji(a,i,k,j);
             }
     }
 
void msort() {
     msort(lista.zivotinja,0,br-1);
     }