如何对链表进行归并排序

1. Overview

In this tutorial, we’ll discuss sorting a linked list using the merge sort algorithm.

Firstly, we’ll define the problem and provide an example that explains it.

Secondly, we’ll discuss two approaches to this problem.

2. Defining the Problem

Suppose we have a linked list consisting of multiple nodes, each node stores two values:

1. : which represents the value stored in the node.
2. : which represents a pointer to the next node that comes after the current node in the list.

Our task is to sort this linked list using the merge sort algorithm so that each node of the list has a value greater than all the previous nodes’ values.

Let’s check an example for better understanding. Suppose we have the following linked list :

After sorting the given linked list, we’ll get the following linked list:

As we can see, each node has a value greater than all the previous nodes’ values.

3. Recursive Approach

3.1. Main Idea

In this approach, we’ll split the given linked list into two halves by making the value of the middle node of the list equal to , then we’ll call our recursive sort function on each half separately, at the end of each call we’ll merge the two sorted halves to get our linked list sorted.

3.2. Implementation

We’re going to divide our implementation into three functions. First, we’ll implement a function that returns the middle element in a list. Next, we’ll see who to merge two sorted lists. Finally, we’ll explain the complete algorithm.

3.3. Get Middle of Linked List

Let’s take a look at the implementation:

algorithm Get_Middle(head):
    // INPUT
    //    head = the first node of the linked list
    // OUTPUT
    //    the middle node of the linked list
    slow <- head
    fast <- head
    while fast != null and fast.next != null:
        slow <- slow.next
        fast <- fast.next.next
    
    return slow

The function will return the middle node of a linked list.

We defined two pointers, slow and fast. Each time, the slow pointer moves one step forward, and the fast one moves two steps forward. So, the fast pointer will move twice the distance that the slow pointer did, which means when the fast pointer reaches the end of the linked list, the slow one will be located at the middle of the linked list.

3.4. Merge Two Sorted Linked Lists

Let’s take a look at the implementation:

algorithm Merge(L1, L2):
    // INPUT
    //    L1 = the first sorted linked list
    //    L2 = the second sorted linked list
    // OUTPUT
    //    A new linked list that merges L1 and L2 in sorted order
    
    new_list <- null
    tail <- null
    
    while L1 != null and L2 != null:
        next_node <- null
        
        if L1.data <= L2.data:
            next_node <- L1
            L1 <- L1.next
        else:
            next_node <- L2
            L2 <- L2.next
        
        if tail != null:
            tail.next <- next_node
        else:
            newList <- next_node
            tail <- next_node
        
        tail <- tail.next
    
    if L1 != null:
        tail.next <- L1
    else:
        tail.next <- L2
    
    return new_list

The function will merge two sorted lists into a single sorted linked list.

First, we declared a linked list and , which is a pointer to the end of the .

Next, while the current pointers and not equal to we have to maintain two situations:

1. : which means the current node of the list should go before the node of the list because it has a value smaller than or equal to the value of node. Therefore, the should be the current node, and we move pointer to the next node.
2. : then the should be the current node, and we move pointer to the next node.

After that, we’ll append the to the of the .

When one of the pointers reaches the end of its list, we break out of the loop. Then, we check if one of the pointers still not equal to , we append the rest of its list to the end of .

Finally, we’ll return the , which is the head pointer of our merged list.

3.5. Merge Sort a Linked List

Let’s take a look at the implementation:

algorithm Merge_Sort(L):
    // INPUT
    //    L = the linked list to sort
    // OUTPUT
    //    The sorted linked list
    if head = null or head.next = null:
        return head
    middle <- Get_Middle(head)
    left_list <- head
    right_list <- middle.next
    middle.next <- null
    left_list <- MergeSort(left_list)
    right_list <- MergeSort(right_list)
    return Merge(left_list, right_list)

First, we check if equals , then the list is empty. Similarly, if equals , which means there is a single node in the given list. In both case scenarios, the sorted version of the list would still be the same as the initial one, so we return the .

Next, we’ll get the middle node of the list using the function. Then, we’ll split the given list into two parts:

1. : which starts at the pointer.
2. : which starts after the middle node .

After that, we’ll make equal to to cut the list from the middle node into two halves.

Eventually, we sort each part separately, then we’ll merge them to get a single sorted list.

3.6. Complexity

The time and space complexity here is . Let’s examine the reason behind this complexity.

First, the function has a complexity cause we iterate over each node of the list at most once, where is the length of the list.

Second, the function has a complexity cause we iterate over the node of each list at most once, where is the length of the first list and the length of the second one.

Finally, the function has a complexity cause in each call, we merge two lists with the complexity of and the depth of recursive tree will be because in each call we split our list into two halves, where is the length of the list.

which means the total complexity is .

4. Iterative Approach

4.1. Main Idea

In this approach, we’ll divide the given linked list into sorted blocks of size powers of two, then we’ll merge every two consecutive blocks together.

First, we divide the list into blocks of size one, then we’ll merge every two consecutive blocks together, so we get blocks of size two sorted.

Second, we divide the list into blocks of size two, then we’ll merge every two consecutive blocks together, so we get blocks of size four sorted.

We keep doing these steps until the block size reaches the first power of two that is greater than or equal to the length of the given linked list, in that moment, our linked list will be sorted.

4.2. Implementation

We’re going to divide our implementation into two functions. The first one is responsible for merging two blocks, while the second is the complete algorithm itself.

4.3. Merge Two Blocks

Let’s take a look at the implementation:

algorithm Merge_Blocks(left, leftSize, right, rightSize, L, tail):
    // INPUT
    //    left = the start of the left block
    //    left_size = size of the left block
    //    right = the start of the right block
    //    right_size = size of the right block
    //    L = the linked list being sorted
    //    tail = the current tail of the sorted linked list
    // OUTPUT
    //    the merged blocks as part of the linked list L
    while not Empty(left) or not Empty(right):
        next_node <- null
        if Compare(left, right):
            next_node <- left
            left <- left.next
            left_size <- left_size - 1
        else:
            next_node <- right
            right <- right.next
            rightSize <- right_size - 1
        nextNode.next <- null
        if tail != null:
            tail.next <- next_node
        else:
            L <- next_node
            tail <- next_node
        tail <- tail.next

The function will merge two sorted blocks of a specific size. This function’s parameters are a pointer to the beginning of the first block and its size. In addition, we pass the same for the second block. Finally, we pass the linked list and a pointer to its end.

As long as one of the blocks is not empty, it means there are still some untaken nodes in these blocks, so we perform multiple steps.

First, we declare , which will store the node that should come after the last node in the list .

Second, we call the function which checks if the block is empty or there still some untaken nodes in the block. In addition, it checks whether the value of the current node is less than or equal to the value of the current node, which means the node should come before the one.

If so, we assign the node to the and decrease the size of the block by one and move the pointer to the next node. Otherwise, the will be the one; we decrease the size of the block by one and move the pointer to the next node.

Finally, we make equal to to cut the node out of the block, and append it to the end of the linked list .

4.4. Merge Sort a Linked List

Let’s take a look at the implementation:

algorithm Iterative_Merge_Sort(L):
    // INPUT
    //    L = the linked list to sort
    // OUTPUT
    //    the sorted linked list
    block_size <- 1
    block_count <- infinity
    while block_count > 1:
        block_count <- 0
        left <- L
        right <- L
        L <- null
        tail <- null
        while left != null:
            block_count <- block_count + 1
            left_size <- 0
            right_size <- block_size
            while left_size < block_size and right != null:
                right <- right.next
                left_size <- left_size + 1
            Merge_Blocks(left, left_size, right, right_size, L, tail)
            left <- right
    return L

Initially, we declare which represents the size of each block of the list after dividing it, and which represents the number of merged blocks after merging every two consecutive blocks.

Next, as long as we didn’t reach the first power of two that is greater than or equal to the length of the given linked list, we have to do the following steps:

1. Reset the value of to zero.
2. Declare left and right pointers that point to the start of the linked list initially.
3. Clear the list .
4. While the left block size is smaller than and the pointer didn’t reach the end of the list, we move the pointer to the next node of the list and increase the size of the left block by one. Now, the information is at the beginning of the first block and the pointer is at the beginning of the second block.
5. Merge the first and the second blocks.
6. Make since the pointer after merging points to the beginning of the block that comes after the second block.
7. Repeat all these steps until we merge the whole list meaning that the linked list is sorted.

4.5. Complexity

Space complexity here is since we’re modifying the same list and didn’t create any additional list. Let’s examine the reason behind this complexity.

Regarding time complexity, we keep dividing the given linked list into blocks times, until we reach the first power of two that is greater than or equal to the length of the linked list. Next, in each iteration, we merge every two consecutive blocks which the sum of their length in total equal to .

which means the total complexity is .

5. Conclusion

In this tutorial, we presented the problem of sorting a linked list using the merge sort algorithm. We explained the general idea and discussed two approaches to solve it.