Shortest merge sort (in place, stable)

list_merge_sort.py

def list_merge_sort(l, start, end):
    if start >= end - 1: return l

    m = (start + end) // 2
    l = list_merge_sort(l, start, m)
    l = list_merge_sort(l, m, end)

    start_head = l
    start_parent = None
    mid_head = l 
    end_head = l

    count = 0
    while count != end:
        if count < start:
            start_parent = start_head
            start_head = start_head.next
        if count < m:
            mid_head = mid_head.next
        end_head  = end_head.next
        count += 1

    new_head = None
    p_left = start_head
    p_right = mid_head

    while p_left != mid_head and p_right != end_head:
        smaller = p_left if p_left.val < p_right.val else p_right
        if new_head:
            new_head.next = smaller
            new_head = new_head.next
        else:
            new_head = smaller
            if start_parent:
                start_parent.next = new_head
            else:
                l = new_head
        if smaller == p_left:
            p_left = p_left.next
        else:
            p_right = p_right.next

    while p_left != mid_head:
        new_head.next = p_left
        new_head = new_head.next
        p_left = p_left.next

    while p_right != end_head:
        new_head.next = p_right
        new_head = new_head.next
        p_right = p_right.next

    new_head.next = end_head
    return l
            

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

a = Node(5)
b = Node(10)
c = Node(3)
d = Node(1)
e = Node(9)

a.next = b
b.next = c
c.next = d
d.next = e

res = list_merge_sort(a, 0, 3)
while res:
    print(res.val, end=' ')
    res = res.next
print()

merge_sort.js

function sort(arr, start, end) {
    if (start >= end-1) return;
    var mid = start + ~~((end-start)/2);
    // after calling this
    // left half and right half are both sorted
    sort(arr, start, mid);
    sort(arr, mid, end);
    
    /**
     * Now we can do the merging
     */
    
    // holding merged array
    // size = end-start
    // everything here will be copied back to original array
    var cache = Array(end-start).fill(0);
    var k=mid;
    // this is O(n) to arr[start:end]
    for (var i=start, r=0;i<mid;r++,i++) {
        while (k<end && arr[k] < arr[i]) cache[r++] = arr[k++];
        cache[r] = arr[i];
    }
    // k marks the position of the element in the right half that is bigger than all elements in the left
    // effectively it tells that we should only copy start~start+k element from cache to nums
    // because the rests are the same
    for (var i=0;i<k-start;i++) arr[i+start]=cache[i];
}

quick_sort.py

def quick_sort(arr, start, end):
    if start >= end - 1:
        return

    p = (start + end) // 2 
    swap(arr, p, end - 1)

    l = start
    r = end - 1
    while l < r:
        if arr[l] < arr[end-1]:
            l += 1
        else:
            r -= 1
            swap(arr, l, r)
    swap(arr, r, end-1)
    quick_sort(arr, start, r)
    quick_sort(arr, r + 1, end)

def swap(arr, f, t):
    tmp = arr[f]
    arr[f] = arr[t]
    arr[t] = tmp
    
    
arr = [9,7,4,3,4,5,6,7,8,6,5,4,3,5,5,43,3,3,4,54,6]
# arr = [4,3]
quick_sort(arr, 0, len(arr))
print(arr)