---
title: "merge sort"
source: https://www.jemoka.com/posts/kbhmerge_sort/
---

merge sort is a Divide and Conquer algorithm for sorting.
intuition take a list, and split in half recursively, call merge sort in each half merge them together using two pointer method (i.e. advance pointer when one is smaller than the other) requirements def merge(a,b): ptr1 = 0 ptr2 = 1 new = [] # use two pointers, ... def mergesort(a): n = len(a) if n &lt;= 1: return a l = mergesort(a[0: n/2]) r = mergesort(a[n/2: n]) return merge(l,r) additional information correctness Induction.
Hypothesis: every recursive call on an array of at most length i, mergesort works.
Base case: 1 element array is sorted.
Step: If IH holds for all \(0 &lt; i &lt; k\), then it holds for \(i=k\).
performance \(\log n\) levels, merge each takes \(n\).
