Merge Sort

切割，合併。

其實在搜尋前都要先排序。

背景知識

雙指針
遞迴

理解問題

遞增排序

思路視覺化

切割 Divide
[5,3,8,6,2,7,1,4] 一直切半至單體

合併 Merge
雙指針兩兩比大小，加入小的

[2,7,1,4] -> [1,2,4,7]

left: [2,7, inf]
right: [1,4, inf]

2>1, r= 4 , [1,0,0,0]
4>2, l= 7, [1,2,0,0]
7>4, r= inf, [1,2,4,0]
inf>7, l= inf, [1,2,4,7]

Java

• LinkedList

TC: O(nlogn): Devide 一直切半(logn)至單體，合併O(n)
SC: O(n)

import java.io.*;
import java.lang.*;
import java.util.*;
 
class Node {
    int data;
    Node next;
    Node(int data){
        this.data = data;
        next = null;
    }
}
 
class MergeSort {
    static Node merge(Node left, Node right){
        Node result = new Node(-1); // init value -1
        Node temp = result;
       
        while (left != null && right != null) {
            // add smallest from two arrays
            if (left.data < right.data) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            // go next
            temp = temp.next;
        }
        
        // remain
        while (left != null) {
            temp.next = left;
            left = left.next;
            temp = temp.next;
        }
        while (right != null) {
            temp.next = right;
            right = right.next;
            temp = temp.next;
        }
        return result.next;
    }
    static void printList(Node head){
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
    // fast slow pointer, fast reach end, slow is half
    static Node findMid(Node head){
        Node slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    static Node sort(Node head){
        if (head.next == null) return head;
 
        Node mid = findMid(head);
        
        Node left = head;
        Node right = mid.next;
        mid.next = null;

        Node resultHead = merge(sort(left), sort(right));
        return resultHead;
    } 
    public static void main(String[] args){
        // construct list {5,3,8,6,2,7,1,4}
        Node head = new Node(5);
        Node temp = head;
        temp.next = new Node(3);
        temp = temp.next;
        temp.next = new Node(8);
        temp = temp.next;
        temp.next = new Node(2);
        temp = temp.next;
        temp.next = new Node(7);
        temp = temp.next;
        temp.next = new Node(1);
        temp = temp.next;
        temp.next = new Node(4);
        temp = temp.next;

        head = sort(head);
        System.out.println("\nSorted Linked List is: ");
        printList(head);
    }
}
>
java -cp /tmp/DdaOkvSxtV MergeSort
Sorted Linked List is: 
1 2 3 4 5 7 8 

• Array

import java.util.*;
class MergeSort {
    private static void merge(int[] arr, int[] left,int[] right){
        int i=0, l=0, r=0;

        while(l<left.length && r<right.length){
           // add smallest from two arrays
           if(left[l]<right[r])
              arr[i++] = left[l++];
           else
              arr[i++] = right[r++];
       }
       // remain
       while(l<left.length)
         arr[i++] = left[l++];
       while(r<right.length)
         arr[i++] = right[r++];
    }
    private static void sort(int [] arr){
      if(arr.length <= 1) return;
      int mid = arr.length /2;
      
      // CopyOfRange is O(N)   
      int [] left = Arrays.copyOfRange(arr,0,mid); 
      int [] right = Arrays.copyOfRange(arr,mid,arr.length);
      
      sort(left);
      sort(right);
      
      merge(arr,left,right);
    }
    public static void main(String[] args) {
        int [] arr = {5,3,8,6,2,7,1,4};
        sort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
>
java -cp /tmp/fqlpjpJwBO MergeSort
1 2 3 4 5 6 7 8 

Python

TC: O(nlogn): Log base is 2, half each time.
SC: O(logn): Store each single item.

def merge(left, right):

    result = []
    
    while len(left) and len(right):
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # remain
    result = result+left if len(left) else result+right # 添加小的到結果
    return result

def mergeSort(array):

    # Devide
    if len(array) < 2: return array
    mid = len(array)//2
    return merge(mergeSort(array[:mid]),mergeSort(array[mid:]))

print(mergeSort([5,3,8,6,2,7,1,4]))

> [1, 2, 3, 4, 5, 6, 7, 8]

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)