I am trying to implement an insertion sort on STL lists. My implementation runs fine until it reaches a certain value and it just removes a couple values from the list while still sorting some of the other ones. I am very confused about what is happening. I am in the process of reinstalling cygwin because I forgot to install gdb. If anyone could give me any pointers as to what I am doing wrong, I would really appreciate it.
Here is the code for the function
void insertionsort(list<T>& lst) {
// iterator that will reference the end of the
// sorted portion of the list
class list<T>::iterator sortedEnd = lst.begin();
// this iterator will be used to point to the next node
// that is after the end of the sorted portion of the list
class list<T>::iterator nextNode = lst.begin();
// increment the nextNode iterator to the second element because
// it is assumed that the first element is already sorted
nextNode++;
// this iterator will be used to traverse the already-sorted
// portion of the list, seeking the correct insertion spot for
// the next unsorted value
class list<T>::iterator it = lst.begin();
while (nextNode != lst.end()) {
// determine if the value of the node pointed to by nextNode
// is smaller than the last value of the sorted portion of
// the list, if it is, the nextNode value needs to be placed
// somewhere in the sorted portion of the list
if (*sortedEnd > *nextNode) {
// the nextNode value belongs in the sorted portion of the
// the list
//store the value that nextNode points to
T value = *nextNode;
nextNode = lst.erase(nextNode);
// traverse the sorted portion of the list to determine where
// the nextNode value should be place
bool notFound = true;
it = lst.begin();
while (it != sortedEnd && notFound) {
if (*it > value) {
lst.insert(it, value);
notFound = false;
}
it++;
}
} else {
// the current value is sorted properly, increment the
// sortedEnd iterator to point to the next value to
// move the range of the sorted portion of the list
sortedEnd++;
}
// point the nextNode iterator the next value after the
// sorted portion of the list
nextNode = sortedEnd;
nextNode++;
}
} // end function
Here is the output, first line is unsorted list and second
line is list after function call
