home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / kill2.zip / kill2src.zip / lnksort.c < prev    next >
C/C++ Source or Header  |  1992-12-21  |  1KB  |  54 lines
  1.  
  2.  
  3. /* linked list sort -- public domain by Ray Gardner  5/90  -- modified */
  4.  
  5. #include <stdio.h>              /* for NULL definition */
  6. #include <time.h>
  7.  
  8.   struct __filelist2__ {
  9.     char   *filename;
  10.     time_t filedate;
  11.     struct __filelist2__ *next;
  12.   };
  13.  
  14. /* split list into 2 parts, sort each recursively, merge */
  15.  
  16. struct __filelist2__ *msortl (struct __filelist2__ *p) {
  17.  
  18.    struct __filelist2__ *q, *r, *head;
  19.  
  20.    if ( p ) {                           /* first split it */
  21.       r = p;
  22.       for ( q = r->next; q && (q = q->next) != NULL; q = q->next )
  23.          r = r->next;
  24.       q = r->next;
  25.       r->next = NULL;
  26.       if ( q ) {                        /* now sort each sublist */
  27.          p = msortl(p);
  28.          q = msortl(q);
  29.          if (q->filedate < p->filedate) {     /* smallest item becomes list head */
  30.             head = q;
  31.             q = q->next;
  32.          } else {
  33.             head = p;
  34.             p = p->next;
  35.          }
  36.          for (r = head; p && q; ) {    /* now merge the lists under head */
  37.             if (q->filedate < p->filedate) {
  38.                r->next = q;
  39.                r = q;
  40.                q = q->next;
  41.             }
  42.             else {
  43.                r->next = p;
  44.                r = p;
  45.                p = p->next;
  46.             }
  47.          }
  48.          r->next = (p ? p : q);       /* append the leftovers */
  49.          p = head;
  50.       }
  51.    }
  52.    return p;
  53. }
  54.