# Sort a Singly Linked List

## Sorting a Singly Linked List

Sorting a singly linked list involves arranging the nodes in the list in a specific order, typically in ascending or descending order. This can be achieved using various sorting algorithms adapted for linked lists. Common algorithms for sorting linked lists include merge sort and bubble sort.

## Step-by-Step Process for Merge Sort

Merge sort is an efficient, stable, and comparison-based sorting algorithm that works well with linked lists due to its divide-and-conquer approach. The process involves recursively splitting the list into halves, sorting each half, and merging the sorted halves.

**Split the List**: Use the slow and fast pointer technique to find the middle of the list and split it into two halves.**Sort Each Half**: Recursively sort each half of the list.**Merge Sorted Halves**: Merge the two sorted halves into a single sorted list.

Consider a singly linked list with the following structure before sorting:

```
Head -> 4 -> 2 -> 1 -> 3 -> None
```

After sorting, the list will become:

```
Head -> 1 -> 2 -> 3 -> 4 -> None
```

## Python Program to Sort a Singly Linked List using Merge Sort

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def merge_sort(self, head):
if head is None or head.next is None:
return head
middle = self.get_middle(head)
next_to_middle = middle.next
middle.next = None
left = self.merge_sort(head)
right = self.merge_sort(next_to_middle)
sorted_list = self.sorted_merge(left, right)
return sorted_list
def get_middle(self, head):
if head is None:
return head
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def sorted_merge(self, a, b):
result = None
if a is None:
return b
if b is None:
return a
if a.data <= b.data:
result = a
result.next = self.sorted_merge(a.next, b)
else:
result = b
result.next = self.sorted_merge(a, b.next)
return result
def sort(self):
self.head = self.merge_sort(self.head)
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(4)
linked_list.append(2)
linked_list.append(1)
linked_list.append(3)
print("Linked list before sorting:")
linked_list.traverse() # Output: 4 -> 2 -> 1 -> 3 -> None
linked_list.sort()
print("Linked list after sorting:")
linked_list.traverse() # Output: 1 -> 2 -> 3 -> 4 -> None
```

This Python program defines a singly linked list with methods for appending nodes, sorting the list using merge sort, and traversing the list. The merge_sort method recursively splits the list into halves, sorts each half, and merges the sorted halves to produce a sorted list.