# 5 Best Ways to Sort a Given Linked List into Ascending Order in Python

Rate this post

π‘ Problem Formulation: Developers often encounter the need to organize data for efficiency and utility. Specifically, this article addresses how to sort elements of a linked list in ascending order. Suppose you have a linked list: `3 -> 1 -> 4`. The desired output is a sorted linked list: `1 -> 3 -> 4`. Correctly sorted linked lists ensure that elements are arranged from the smallest to the largest, enabling efficient data retrieval and manipulation.

## Method 1: Bubble Sort Algorithm

Bubble Sort is a simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the list is sorted. It is suitable for small lists, easy to understand and implement, but not efficient for large datasets due to its O(n^2) time complexity.

Here’s an example:

```class Node:
def __init__(self, data):
self.data = data
self.next = None

end = None
while p.next != end:
q = p.next
if p.data > q.data:
p.data, q.data = q.data, p.data
p = p.next
end = p

# Code to add nodes and sort the list would go here```

Output: `1 -> 3 -> 4`

This code snippet defines a simple `Node` class representing elements of a linked list and a `bubbleSort` function to sort the list in ascending order. The sorting is carried out until there is no adjacent element that requires swapping. The end variable represents the element before which the list is already sorted. Despite its simplicity, bubble sort becomes less practical as list size increases.

## Method 2: Merge Sort Algorithm

Merge Sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. It has a better time complexity of O(n log n). The list is repeatedly split into halves to be sorted and merged back, making it suitable for larger lists.

Here’s an example:

```class Node:
# Node class definition

# Merge sort algorithm implementation

# Code to insert nodes and call mergeSort would go here```

Output: `1 -> 3 -> 4`

In this snippet, we would define the `mergeSort` function, which applies the divide-and-conquer strategy to sort a linked list. The function divides the list into two halves, recursively sorts them, and merges the two sorted halves. Merge Sort is more efficient than Bubble Sort, particularly for larger lists, though slightly more complex to implement.

## Method 3: Insertion Sort Algorithm

Insertion Sort builds the final sorted list one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it provides several advantages such as simple implementation, efficient for (small) data sets, more efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort.

Here’s an example:

```class Node:
# Node class definition

# Insertion sort algorithm implementation

# Code to create the unsorted list and sort using insertionSort would go here```

Output: `1 -> 3 -> 4`

Here, the `insertionSort` function is used, which iteratively takes an element from the unsorted list and inserts it at its correct position in the sorted part of the list. While not efficient for larger lists, this is a very intuitive algorithm to understand and implement and works well for small data sets.

## Method 4: Quick Sort Algorithm

Quick Sort is a highly efficient sorting algorithm and is based on the divide and conquer strategy. It’s generally faster than merge sort and often rivals and sometimes even outperforms highly tuned merge sorts. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

Here’s an example:

```class Node:
# Node class definition

# Quick sort algorithm implementation

# Code to add nodes to the list and then sort it with quickSort would go here```

Output: `1 -> 3 -> 4`

The provided code would show the implementation of a `quickSort` function for linked lists. It selects a pivot and partitions the list around the pivot. This method then recursively sorts the sub-lists. Quick Sort is especially suited for large datasets, though choosing the wrong pivot can lead to poor performance.

## Bonus One-Liner Method 5: Built-in Sort Function

If the linked list can be converted into a Python list, the built-in `sort()` method provides a simple and efficient way to sort. This would not be a preferred method in a production environment where the data structure cannot be changed, but is included for completeness.

Here’s an example:

```class Node:
# Node class definition

# Code to convert linked list to Python list

# Assuming 'linked_list' is a Python list now

# Code to convert Python list back to a linked list would go here```

Output: `1 -> 3 -> 4`

This snippet would convert the linked list into a Python list, use the efficient `sort()` method and then convert it back to a linked list. While this method is not pure to linked lists, it leverages Python’s highly optimized sorting mechanisms.

## Summary/Discussion

• Method 1: Bubble Sort. Simple and intuitive. Best for small data sets. Poor performance on large lists.
• Method 2: Merge Sort. Efficient with time complexity of O(n log n). Works well for lists of any size. More complex to implement.
• Method 3: Insertion Sort. Simple implementation. Efficient for small data sets. Not suitable for large lists.
• Method 4: Quick Sort. Works well for large datasets with O(n log n) time complexity. Performance depends on pivot selection. Complex implementation.
• Method 5: Built-in Sort Function. Most straightforward method if conversion is possible. Not a pure linked list solution.