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

    while(cin>>n)
    {
        // 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 while

    return head;
}