/*============================================================================================================================================================================

                        Sort Label or Symbol Table

        First Sort by Name so that it can check for Duplicated Symbols, then Sort by Value,
        Check for Duplicates, and set up Pointer Array for Binary Search.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

struct sym *sort(struct sym *list, SYM_PTR *array, word count){
        word    i;
        struct sym      *srtptr, *temp;

        srtptr = sort_by_name(list);        chk_dup_name (srtptr, count);
        srtptr = sort_by_value(srtptr);     chk_dup_value(srtptr, count);
        temp = srtptr;
        for (i=0; inext; }                                          /* Set up Array of Pointers Sorted by Value */
        return(srtptr);
}

/*============================================================================================================================================================================

                In-place Non-recursive Merge Sort using Label Text as Key

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

struct sym *sort_by_name(struct sym *list){
        word            i, n;
        struct sym      *a, *b, *todo, *t;

        head_ptr = (struct sym *) malloc(sizeof(struct sym) + 12);
        head_ptr->next = list;
        a = tail_ptr;
        for (n=1; a != head_ptr->next; n = n + n){
                todo = head_ptr->next;
                list = head_ptr;
                while (todo != tail_ptr){

                        t = todo;
                        a = t;
                        for (i=1; inext;
                        b = t->next;
                        t->next = tail_ptr;

                        t = b;
                        for (i=1; inext;
                        todo = t->next;
                        t->next = tail_ptr;

                        list->next = merge_by_name(a, b);
                        for (i=1; i<=n+n; i++) list = list->next;
                }
        }
        return(head_ptr->next);
}

/*============================================================================================================================================================================

                In-place Non-recursive Merge Sort using Value as Key

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

struct sym *sort_by_value(struct sym *list){

        word            i, n;
        struct sym      *a, *b, *todo, *t;

        head_ptr = (struct sym *) malloc(sizeof(struct sym));
        head_ptr->next = list;
        a = tail_ptr;
        for (n=1; a != head_ptr->next; n = n + n){
                todo = head_ptr->next;
                list = head_ptr;
                while (todo != tail_ptr){

                        t = todo;
                        a = t;
                        for (i=1; inext;
                        b = t->next;
                        t->next = tail_ptr;

                        t = b;
                        for (i=1; inext;
                        todo = t->next;
                        t->next = tail_ptr;

                        list->next = merge_by_value(a, b);
                        for (i=1; i<=n+n; i++) list = list->next;
                }
        }
        return(head_ptr->next);
}

/*============================================================================================================================================================================

                Merge Sub-lists by Text Field

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

struct sym *merge_by_name(struct sym *a, struct sym *b){

        int                     i;
        struct sym      *c;

        c = tail_ptr;
        do{
                i = stricmp(a->label, b->label);
                if (i <= 0){
                        c->next = a;
                        c = a;
                        a = a->next;
                }else{
                        c->next = b;
                        c = b;
                        b = b->next;
                }
        } while (c != tail_ptr);
        c = tail_ptr->next;
        tail_ptr->next = tail_ptr;
        return(c);
}

/*============================================================================================================================================================================

                Merge sub-lists by value field

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

struct sym *merge_by_value(struct sym *a, struct sym *b){

        struct sym      *c;

        c = tail_ptr;
        do{
                if (a->adrs < b->adrs){
                        c->next = a;
                        c = a;
                        a = a->next;
                }else{
                        c->next = b;
                        c = b;
                        b = b->next;
                }
        } while (c != tail_ptr);
        c = tail_ptr->next;
        tail_ptr->next = tail_ptr;
        return(c);
}