```void InsertSort(struct node** headRef) {
struct node* result = NULL; // build the answer here
struct node* current = *headRef; // iterate over the original list
struct node* next;

while (current!=NULL) {
next = current->next; // tricky - note the next pointer before we change it
SortedInsert(&result, current);
current = next;
}
}

/ Dummy node strategy for the head end
void SortedInsert2(struct node** headRef, struct node* newNode) {
struct node dummy;
struct node* current = &dummy;

while (current->next!=NULL && current->next->data < newNode->data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;

}
```
``````void MergeSort(struct node** headRef) {
struct node* a;
struct node* b;
// Base case -- length 0 or 1
return;
}
FrontBackSplit(head, &a, &b); // Split head into 'a' and 'b' sublists by slow and fast point
// We could just as well use AlternatingSplit()

MergeSort(&a); // Recursively sort the sublists
MergeSort(&b);
*headRef  = SortedMerge(a, b); // answer = merge the two sorted lists together
}

struct node* SortedMerge3(struct node* a, struct node* b) {
struct node* result = NULL;
// Base cases
if (a==NULL) return(b);
else if (b==NULL) return(a);

// Pick either a or b, and recur
if (a->data <= b->data) {
result = a;
result->next = SortedMerge3(a->next, b);
}
else {
result = b;
result->next = SortedMerge3(a, b->next);
}
return(result);
}```
```

selection sort by swap values

```//Assume HEAD pointer denotes the first element in the linked list
// only change the values…don’t have to change the pointers

{
node* first,second,temp,min;
while(first!=null)
{
min = first;
second=first->NEXT;
while(second!=null)
{
if(min->value > second->value)
min = second;
second=second->NEXT;
}
if(min!=first)
swap_value(min,first);

first=first->NEXT;
}
}
```

1)while loop version

```void reverse_single_linked_list(struct node** headRef)
{
struct node* result = NULL;
struct node* next;
while (current != NULL)
{
next = current->next; // tricky: note the next node
current->next = result; // move the node onto the result
result = current;
current = next;
}
}
```

2)recursive version:

```void RecursiveReverse(struct node** headRef) {
struct node* first;
struct node* rest;
if (*headRef == NULL) return; // empty list base case

first = *headRef; // suppose first = {1, 2, 3}
rest = first->next; //         rest = {2, 3}

if (rest == NULL) return; // empty rest base case

RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
// after: rest = {3, 2}

first->next->next = first; // put the first elem on the end of the list
first->next = NULL; // (tricky step -- make a drawing)