# 合併排序法 MergeSort

###### tags: `leetcode`,`sorting`

>ref: https://www.geeksforgeeks.org/in-place-merge-sort/
>

## 基礎流程

1. 分成split/conquer兩方法,藉由分組至單個元素後兩兩比較形成有序排列,持續合併至原方法,範例為遞迴方式呼叫

2. TimeComplexity, 分組行為每次拆為一半, 需log~2~n次=>O(log~2~n),conquer次數同split
合併時需進行比較，假定為兩代合併陣列分別為m,n個元素, 最優情況為其中一組皆小於/皆大於另一組=>比較n或m次o(n),最差情況為m+n-1(每元素皆需比較過O(n))
總時間: 分裂時間+ 合併時間 = O(logN) + O(N* logN)=>省略前向 結果為O(nlog~2~n)


3. spaceComplecity: O(N)
3a.ListNode: 每次merge的dummy head: O(log~2~n)
3b.in-place Array:split記憶middle位置 : O(log~2~n),conquer時 inplace記憶 val/idx : O(log~2~2n)=>O(log~2~3n)

	public ListNode mergesort(ListNode m) {

		// separate the list
		ListNode middle = findMiddle(m);
		ListNode start2 = middle.next;
		middle.next = null;

		
		ListNode left = mergesort(m);
		ListNode right = mergesort(start2);

		return merge(left, right);

	}

ListNode def:

	public class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	public ListNode findMiddle(ListNode n) {
		ListNode a = n;
		ListNode b = n;

		while (b != null && b.next != null) {
			a = a.next;
			b = b.next.next;
		}
		return a;
	}

	public ListNode merge(ListNode left, ListNode right) {

		ListNode head = new ListNode();
		ListNode cur = head;

		// remodel the node
		while (left != null && right != null) {
			if (left.val <= right.val) {
				cur.next = left;
				left = left.next;
			} else {
				cur.next = right;
				right = right.next;
			}
			cur = cur.next;
		}

		// concatenate the remaining list
		if (left == null) {
			cur.next = right;
		} else {
			cur.next = left;
		}

		return head.next;
	}

## inplace array
1. merge時需記憶idx與val做arr內數值移動

	public int[] mergesort(int[] arr) {
		// split helper
		split(arr, 0, arr.length - 1);

		return arr;
	}

	private void split(int[] arr, int s, int e) {

		if (s >= e) {
			return;
		}
		// middle
		int middle = s + (e - s) / 2;

		// split
		split(arr, s, middle);
		split(arr, middle + 1, e);

		// conquer
		merge(arr, s, middle, e);

	}

	private void merge(int[] arr, int s, int middle, int e) {

		int st2 = middle + 1;
		if (arr[middle] <= arr[st2]) {
			return;
		}

		while (s <= middle && st2 <= e) {  //equal condition to compare the last one

			if (arr[s] > arr[st2]) {
				int val = arr[st2];
				int idx = st2;
				while (s < idx) {
					arr[idx] = arr[--idx];
				}
				arr[s] = val;

				middle++;//move backward the original array insert arr[st2], the checking condition should move backward too
				st2++;
			}
			s++;
		}

	}
	}