# An implementation to link-based quick sort and merge sort（by golang） # 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: ```go 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. ![在这里插入图片描述](https://img-blog.csdnimg.cn/9eb866ca9c764d8ba944ad26b2eebc73.png) 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`. ![在这里插入图片描述](https://img-blog.csdnimg.cn/cfcb9b919b4842aa91574b8ac760a3b6.png) 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. ![在这里插入图片描述](https://img-blog.csdnimg.cn/8c9408c765b5445ea4e4cf7bb1f7e545.png) Last, merge `sublist` and `pivot`. ![在这里插入图片描述](https://img-blog.csdnimg.cn/83785c2acca14f00b6f7a471536aefd5.png) Averay Time Complexity：\\(O(n\cdot log(n))\\) Space Complexity：\\(O(1)\\) Codes as follows： ```go 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. ![在这里插入图片描述](https://img-blog.csdnimg.cn/db9939f17a7843c59d8de578f24c5b43.png) 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. ![在这里插入图片描述](https://img-blog.csdnimg.cn/8e8b9fb163724f92bcded3c5aa5f6a54.png) average time complexity：\\(O(n\cdot log(n))\\) the best and the worst time complexity：\\(O(n\cdot log(n))\\) space complexity：\\(O(1)\\) ```go 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. ```go 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： ![在这里插入图片描述](https://img-blog.csdnimg.cn/b2e68e8ef1a7433ca521d7f22c3a3fb2.png)