Question: Update: OK I see it's a bubble sort, but is it less efficient because it doesn't stop when there's no swap on a particular run? It runs until first is null.

Hi, I have a sorting algorithm as follows. My question is, which sorting algorithm is this? I thought it was bubble sort, but it does not do multiple runs. Any idea?
Thanks!

```
//sorting in descending order
struct node
{
    int value;
    node* NEXT;
}
//Assume HEAD pointer denotes the first element in the //linked list
// only change the values…don’t have to change the //pointers

Sort( Node *Head)
{
    node* first,second,temp;
    first= Head;
    while(first!=null)
    {
        second=first->NEXT;
        while(second!=null)
        {
            if(first->value < second->value)
            {
                temp = new node();
                temp->value=first->value;
                first->value=second->value;
                second->value=temp->value;
                delete temp;
            }
            second=second->NEXT;
        }

        first=first->NEXT;
    }
}

```

Answer: 
Let's make the algorithm clearer:

```
Sort {
   first = head;
   while (first ≠ NULL) {
      next = first.next
      while (next ≠ NULL) {
         if (first.value < next.value)
            swap first.value and next.value
         advance next
      }
      advance first
   }
}

```

This is a very inefficient implementation of insertion sort. 

---

Example run revealing the insertion sort characteristics:

```
5 → 2 → 3 → 1 → nil
^   ^
f   n [swap]

2 → 5 → 3 → 1 → nil
^       ^
f       n

2 → 5 → 3 → 1 → nil
^           ^
f           n [swap]

1 → 5 → 3 → 2 → nil
^               ^
f               n

1 → 5 → 3 → 2 → nil   // insert the minimum value 1 to the beginning of the sublist
    ^   ^
    f   n [swap]

1 → 3 → 5 → 2 → nil
    ^       ^
    f       n [swap]

1 → 2 → 5 → 3 → nil  // insert the minimum value 2 to the beginning of the sublist
    ^           ^
    f           n

1 → 2 → 5 → 3 → nil
        ^   ^
        f   n [swap]

1 → 2 → 3 → 5 → nil  // insert the minimum value 3 to the beginning of the sublist
        ^       ^
        f       n

1 → 2 → 3 → 5 → nil  // insert the minimum value 5 to the beginning of the sublist
            ^   ^
            f   n

1 → 2 → 3 → 5 → nil
                ^
                f

```
[Insertion sort](http://en.wikipedia.org/wiki/Insertion_sort)

It's very similar to a bubble sort, except that instead of wapping adjacent pairs of items, you move the smallest item to the head of the list, and then the next smallest item into the second position, and so on.