Sorting of linked list in Java

In this post, we will discuss about sorting of linked list. There are many algorithms available for sorting of linked list.Merge sort is preferred for Linked List because of costly operation for random access of elements. Quick sort is faster in case of indexed based data structures but for non-indexed data structures, performance will be slow.So, because of slow random access of linked list, makes Quick Sort very slow and Heap Sort completely impossible. Merge sort is based on Divide and Conquer strategy. Time complexity of Merge Sort is O(n Log n) . Merge sort requires additional memory space to store the intermediate data.

Before implementation of merge sort for linked list in JAVA, we will see the algorithm and execution process.

Algorithm:

 

  1. If root node is NULL or there is only one element in linked list then return the root node.
  2. If step 1 is false, then call the steps 3 recursively till leftNode and rightNode has only one element .
  3. Divide the linked list into two half, leftNode and rightNode.
  4. Sort the leftNode and rightNode separately.
  5. Merge the sorted leftNode and rightNode in recursive manner.
  6. Finally, point the root node as  merged sorted nodes.

 

By seeing the algorithm based on recursive calls, it’s somewhat hard to understand. Now, to describe this algorithm, we will see the execution process, which will show step-by-step process.

Execution Process: Suppose, we have linked list of type Integer.

We will see the implementation in JAVA. Basically, we will have two methods, sort(root ) and mergeSortedList(left, right). sort() method will break the node into two half and keep calling itself recursively till left node and right node size is equal to 1.Now, merge left node and right node and maintain the increasing order. To merge any node, we should check the each node value of right node with each node value of left node.[Try Yourself]

 

Output:

Original List: [37,19,7,54,76]

After sorting: [7,19,37,54,76]

—————————————————————————————————————-

Hope you like this post. Please leave your comments/suggestions.

You may like –

Top