// insertion sort via a doubly linked list dnode *Sort2(const apvector& numbers) { int n; dnode *current = NULL; dnode *insert = 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 current node using a dnode constructor if(current == NULL) current = new dnode(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(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(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(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(n, current->fore(), current); current->fore()->set_back(insert); current->set_fore(insert); current = insert; } } } // end of while return current; }