// insertion sort via a doubly linked list
dnode<int> *Sort2()
{
    int n;
    dnode<int> *current = NULL;
    dnode<int> *insert = NULL;

    while(cin>>n)
    {
        // when the list is empty, create the current node using a dnode constructor
        if(current == NULL)
            current = new dnode<int>(n, NULL, NULL);

        // n is smaller than currentt->data(), insert a new node before the current node
        else if(n < current->data())
        {
            while(current->back() != NULL && n < current->back()->data())
                current = current->back();

            // insert at the very beginning of the list
            if(current->back() == NULL)
            {
                insert = new dnode<int>(n, current, NULL);
                current->set_back(insert);
                current = insert;
            }

            // insert somewhere between the very begining and the current node of the list
            else
            {
                insert = new dnode<int>(n, current, current->back());
                current->back()->set_fore(insert);
                current->set_back(insert);
                current = insert;
            }
        }

        // n is greater than or equal to current->data(), insert a new node after the current node
        else
        {
            while(current->fore() != NULL && n >= current->fore()->data())
                current = current->fore();

            // insert at the very end of the list
            if(current->fore() == NULL)
            {
                insert = new dnode<int>(n, NULL, current);
                current->set_fore(insert);
                current = insert;
            }

            // insert somewhere between the current node  and the very end of the list
            else
            {
                insert = new dnode<int>(n, current->fore(), current);
                current->fore()->set_back(insert);
                current->set_fore(insert);
                current = insert;
            }
        }

    } // end of while

    return current;
}