What sorting algorithm can be used to sort a linked list?

Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?

Why is Quick Sort preferred for arrays?

Nội dung chính Show

Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
How to sort a linked list using merge sort
Program to sort the elements of the singly linked list
Explanation
Video liên quan

Below are recursive and iterative implementations of Quick Sort and Merge Sort for arrays.

Recursive Quick Sort for array.
Iterative Quick Sort for arrays.
Recursive Merge Sort for arrays
Iterative Merge Sort for arrays

Quick Sort in its general form is an in-place sort (i.e. it doesn’t require any extra storage) whereas merge sort requires O(N) extra storage, N denoting the array size which may be quite expensive. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm.
Comparing average complexity we find that both type of sorts have O(NlogN) average complexity but the constants differ. For arrays, merge sort loses due to the use of extra O(N) storage space.
Most practical implementations of Quick Sort use randomized version. The randomized version has expected time complexity of O(nLogn). The worst case is possible in randomized version also, but worst case doesn’t occur for a particular pattern (like sorted array) and randomized Quick Sort works well in practice.
Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays.
Quick Sort is also tail recursive, therefore tail call optimizations is done.

Why is Merge Sort preferred for Linked Lists?

Below are implementations of Quicksort and Mergesort for singly and doubly linked lists.

Quick Sort for Doubly Linked List
Quick Sort for Singly Linked List
Merge Sort for Singly Linked List
Merge Sort for Doubly Linked List

In case of linked lists the case is different mainly due to difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory.
Unlike array, in linked list, we can insert items in the middle in O(1) extra space and O(1) time if we are given reference/pointer to the previous node. Therefore merge operation of merge sort can be implemented without extra space for linked lists.
In arrays, we can do random access as elements are continuous in memory. Let us say we have an integer (4-byte) array A and let the address of A[0] be x then to access A[i], we can directly access the memory at (x + i*4). Unlike arrays, we can not do random access in linked list.
Quick Sort requires a lot of this kind of access. In linked list to access i’th index, we have to travel each and every node from the head to i’th node as we don’t have continuous block of memory. Therefore, the overhead increases for quick sort. Merge sort accesses data sequentially and the need of random access is low.

Related Articles:

Why quicksort is better than mergesort ?
Know Your Sorting Algorithm | Set 1 (Sorting Weapons used by Programming Languages)
Iterative Merge Sort
Iterative Quick Sort

Thanks to Sayan Mukhopadhyay for providing initial draft for above article. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Sorting

Linked-List-Sorting

Merge Sort

Quick Sort

Practice Tags :

Sorting

Merge Sort

Read Full Article

How to sort a linked list using merge sort

Merge sort is one of the most famous divide-and-conquer sorting algorithms. This algorithm can be used to sort values in any traversable data structure (i.e., a linked list).

Program to sort the elements of the singly linked list

Explanation

In this program, we need to sort the nodes of the given singly linked list in ascending order.

Original list:

Sorted list:

To accomplish this task, we maintain two pointers: current and index. Initially, current point to head node and index will point to node next to current. Traverse through the list till current points to null, by comparing current's data with index's data. If current's data is greater than the index's data, then swap data between them. In the above example, current will initially point to 9 and index will point to 7. Since, 9 is greater than 7, swap the data. Continue this process until the entire list is sorted in ascending order.

Algorithm

Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
Create another class SortList which has two attributes: head and tail.
addNode() will add a new node to the list:
1. Create a new node.
2. It first checks, whether the head is equal to null which means the list is empty.
3. If the list is empty, both head and tail will point to a newly added node.
4. If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list.
sortList() will sort the nodes of the list in ascending order.
1. Define a node current which will point to head.
2. Define another node index which will point to node next to current.
3. Compare data of current and index node. If current's data is greater than the index's data then, swap the data between them.
4. Current will point to current.next and index will point to index.next.
5. Continue this process until the entire list is sorted.
display() will display the nodes present in the list:
1. Define a node current which will initially point to the head of the list.
2. Traverse through the list till current points to null.
3. Display each node by making current to point to node next to it in each iteration.