// insertion sort via a singly linked list
node<int> *Sort1(const apvector<int>& numbers)
{
    int n;
    node<int> *head = NULL;
    node<int> *cursor = NULL;

    for(int i = 0; i < numbers.length(); i++)
    {
        n = numbers[i];     // work on one element from numbers at a time

        // when the list is empty, create the head node using a node constructor
        if(head == NULL)
            head= new node<int>(n, NULL);

        // insert a new node before the head using list_head_insert().
        else if(n < head->data())
            list_head_insert(head, n);

        else    // n is greater than or equal to head->data()
            for(cursor = head; cursor != NULL; cursor = cursor->link())

            // insert a new node at the end or in the middle of the list using list_insert()
            // take advantage of lazy evaluation
                if(cursor->link() == NULL || n >= cursor->data() && n < cursor->link()->data())
                {
                    list_insert(cursor,n);
                    break;
                }
    } // end of for

    return head;
}