introduction

As everyone knows, Quick Sort is an excellent algorithm with average time complexity of \(O(n\cdot log(n))\)。Merge Sort is also a best-known sort algorithm with average time complexity of \(O(n\cdot log(n))\) and worst time complexity of \(O(n\cdot log(n))\)。Becouse of their simple idea and fast performance, we can see them from textbook to some programming library almost everywhere 。

Though they are easy to understant, there are rather terrible implementation difficulties.
The main reason is probably the most implementations use arrays. For reducing memory usage, the original array will be reused at partition phrase and merge phrase such that the space complexity will be $O(1)$。As a result, some diabolic tricks and wicked craft come out, which make code hart to understant and implement and easy to generate bugs in the code.

We introduce linked list because it has naturally reusibility. Under the link-based implementaion, not only the momery usage will be declined, but also the source code without those diabolic tricks and wicked craft will be more similar to the nature of the algorithm . The programmers and the students understant it easily and these algorithms can be easily reimplemented in your program.

the elementary knowledge of Quick Sort and Merge sort is not the key point. And the array-based implementation can be seen in other materials. We will show you how to implement these algorithms based linked list.

the structure of linked-list

the structure of linked-list（take int for instance!）as follows:

type ListNode struct {
    data int             // the data of the node
    next *ListNode // the pointer of the next node
}

type List *ListNode

Quick Sort

First, the linked-list will be split into two child linked-list named sublist and pivot. They are empty in the beginning. Amid them, the value of pivot is the value of the first node of the original linked-list. There is another pointer named node which points to the second node of the original linked-list.

And then, iterate node until it becomes nil. if the value of node less than the value of pivot, we take this node and put it onto the rear of sublist, or this node will put into the rear of pivot. As shown in the following picture, the number 3 is less than 7, so it was put on sublist, and the number 8 is greater than 7 so it was put on pivot.

After iteration, sort linked-list sublist and pivot respectively. We acomplish it by recursive calls. The results after sorting are shown as the folowing figure.

Last, merge sublist and pivot.

Averay Time Complexity：\(O(n\cdot log(n))\)

Space Complexity：$O(1)$

Codes as follows：

func QuickSort(list List) {
    // if linked list is empty or there is only one element in the linked list, sorting is not nessesary.
    if list.next == nil || list.next.next == nil {
        return
    }

    // assign the variable [pivot] equals to the first node and the variable [node] eqauls to the second node
    node := list.next.next
    pivot := list.next
    pivot.next = nil
    sublist := list
    sublist.next = nil

    // arrange the nodes to the before or after of [pivot] by the value in it. 
    // the original linked-list will be split into two linked-list with the head of [sublist] and [pivot]
    for node != nil {
        nodeNext := node.next
        if node.data < pivot.data {
            node.next = sublist.next
            sublist.next = node
        } else {
            node.next = pivot.next
            pivot.next = node
        }
        node = nodeNext
    }

    // sort recursively
    QuickSort(sublist)
    QuickSort(pivot)

    // merge two linked-list into one
    i := list
    for i.next != nil {
        i = i.next
    }
    i.next = pivot
}

Merge Sort

The key to implement merge sort on a linked list is how to quickly find the segmentation point to split the list into two child lists. The method provided in this article only needs to scan the linked list once to determine the split point (as shown in the code).

The algorithm first finds the segmentation point midNode, and this node and its previous nodes are divided into list1, and the subsequent nodes are divided into list2.

And then we sort these two lists recursively. The diagram below.

Finally, merge the sorted list1 and list2. The merging process and details are as follows ：

• The merge process first points list1 and list2 to the first node of the two child lists. Empty the list.
• Then, the nodes with the smaller value in the two lists are picked in turn and put into the list.
• Last, the results of list is what the consequence of merging.

average time complexity：\(O(n\cdot log(n))\)

the best and the worst time complexity：\(O(n\cdot log(n))\)

space complexity：$O(1)$

func MergeSort(list List) {
    // if linked list is empty or there is only one element in the linked list, sorting is not nessesary.
    if list.next == nil || list.next.next == nil {
        return
    }

    // calculating the length of linked list, and finding the split point
    midNode := list
    shouldNext := true
    for i := list.next; i != nil; i = i.next {
        if shouldNext {
            midNode = midNode.next
        }
        shouldNext = !shouldNext
    }

    // split list into list1 and list2
    list1 := list
    list2 := &ListNode{next: midNode.next}
    midNode.next = nil

    // recursive call respectively
    MergeSort(list1)
    MergeSort(list2)

    // merge and combine two child lists
    list1 = list1.next
    list2 = list2.next
    tail := list
    tail.next = nil
    for list1 != nil && list2 != nil {
        if list1.data < list2.data {
            tail.next = list1
            list1 = list1.next
            tail = tail.next
        } else {
            tail.next = list2
            list2 = list2.next
            tail = tail.next
        }
    }

    for list1 != nil {
        tail.next = list1
        list1 = list1.next
        tail = tail.next
    }

    for list2 != nil {
        tail.next = list2
        list2 = list2.next
        tail = tail.next
    }
}

Test

In this blog, the results of the two algorithms are compared with the sorting function of GO language to verify the correctness of the algorithm.

func main() {
    list1 := new(ListNode)
    list2 := new(ListNode)
    array := make([]int, 100)
    // generating 100 numbers randomly
    rand.Seed(time.Now().UnixMicro())
    for i := 0; i < 100; i++ {
        number := rand.Intn(100)
        list1.next = &ListNode{data: number, next: list1.next}
        list2.next = &ListNode{data: number, next: list2.next}
        array[i] = number
    }

    QuickSort(list1)
    MergeSort(list2)
    sort.Ints(array)

    // output, and verify the correctness of the two sorting algorithms
    i1 := list1.next
    i2 := list2.next
    j := 0
    for i1 != nil {
        if i1.data != array[j] {
            panic("list1 not equal")
        }
        if i2.data != array[j] {
            panic("list2 not equal")
        }
        fmt.Print(i1.data, ",")
        i1 = i1.next
        i2 = i2.next
        j++
    }
    fmt.Println()
}

results：