Merge Sort

/*
 * Part of Cosmos by OpenGenus Foundation
 */
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)    
      b[i++] = a[l1++];
   while(l2 <= high)   
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
}
void sort(int low, int high) {
   int mid; 
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else { 
      return;
   }   
}
int main() { 
   int i;
   printf("List before sorting\n"); 
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
   sort(0, max);
   printf("\nList after sorting\n"); 
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
}

/*
 Part of Cosmos by OpenGenus Foundation
 merge sort synopsis
namespace merge_sort_impl {
    template<typename _Random_Acccess_Iter>
    _Random_Acccess_Iter
    advance(_Random_Acccess_Iter it, std::ptrdiff_t n);
}
template<typename _Random_Acccess_Iter, typename _Compare>
void mergeSort(_Random_Acccess_Iter begin, _Random_Acccess_Iter end, _Compare comp);
template<typename _Random_Acccess_Iter>
void mergeSort(_Random_Acccess_Iter begin, _Random_Acccess_Iter end);
 */
#include <list>
#include <iterator>
#include <cstddef>
namespace merge_sort_impl {
    template<typename _Random_Acccess_Iter>
    _Random_Acccess_Iter
    advance(_Random_Acccess_Iter it, std::ptrdiff_t n)
    {
        std::advance(it, n);
        return it;
    }
    template<typename _Random_Acccess_Iter, typename _Compare>
    void merge(_Random_Acccess_Iter begin,
               _Random_Acccess_Iter end,
               _Compare comp)
    {
        using value_type = typename std::iterator_traits<_Random_Acccess_Iter>::value_type;
        auto end1 = begin;
        std::advance(end1, std::distance(begin, end) >> 1);
        auto begin1 = begin,
             begin2 = end1,
             end2 = end;
        std::list<value_type> tmp{};
        while (begin1 < end1 &&  begin2 < end2)
            tmp.push_back(comp(*begin1, *begin2) ? *begin1++ : *begin2++);
        while (begin1 < end1)
            *--begin2 = *--end1;
        while (!tmp.empty())
        {
            *--begin2 = tmp.back();
            tmp.pop_back();
        }
    }
}
template<typename _Random_Acccess_Iter, typename _Compare>
void
mergeSort(_Random_Acccess_Iter begin, _Random_Acccess_Iter end, _Compare comp)
{
    size_t dist = std::distance(begin, end);
    if (dist > 1)
    {
        auto mid = begin;
        std::advance(mid, dist >> 1);
        mergeSort(begin, mid, comp);
        mergeSort(mid, end, comp);
        merge_sort_impl::merge(begin, end, comp);
    }
}
template<typename _Random_Acccess_Iter>
void
mergeSort(_Random_Acccess_Iter begin, _Random_Acccess_Iter end)
{
    using value_type = typename std::iterator_traits<_Random_Acccess_Iter>::value_type;
    mergeSort(begin, end, std::less<value_type>());
}

/* Java program for Merge Sort */
// Part of Cosmos by OpenGenus Foundation
class MergeSort {
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    private void merge(int arr[], int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;
        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];
        /*Copy data to temp arrays*/
        System.arraycopy(arr, l + 0, L, 0, n1);
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];
        /* Merge the temp arrays */
        // Initial indexes of first and second subarrays
        int i = 0, j = 0;
        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    // Main function that sorts arr[l..r] using
    // merge()
    private void sort(int arr[], int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l+r)/2;
            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);
            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
    /* A utility function to print array of size n */
    private static void printArray(int arr[]) {
        int n = arr.length;
        for (int anArr : arr) System.out.print(anArr + " ");
        System.out.println();
    }
    // Driver method
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        System.out.println("Given Array");
        printArray(arr);
        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length-1);
        System.out.println("\nSorted array");
        printArray(arr);
    }
}

# Part of Cosmos by OpenGenus Foundation
# Split array in half, sort the 2 halves and merge them.
# When merging we pick the smallest element in the array.
# The "edge" case is when one of the arrays has no elements in it
# To avoid checking and breaking the look, finding which array has elements and then
# Starting another loop, we simply alias the arrays. This abstracts the issue without 
# Creating a mess of code. When we alias, we decide with Xor which array to pick,
# Since we cover 0 ^ 0 case in the beginning of the loop,
# while bool(a) or bool(b) makes 0^0 is impossible to happen, Xor has 3 cases, 1 ^ 0, 0 ^ 1, 1^1 to evaluate. 
# Since the 2 first cases are the edge we go inside the loop and alias the array that has elements in it. 
# If it's 1^1 we simply pick the array with the smallest element.
from random import randint
def merge_sort(array):
    if len(array) == 1:
        return array
    left = merge_sort(array[:(len(array)//2)])
    right = merge_sort(array[(len(array)//2):])
    out = []
    while bool(left) or bool(right):
        if bool(left) ^ bool(right):
            alias = left if left else right
        else:
            alias = left if left[0] < right[0] else right
        out.append(alias[0])
        alias.remove(alias[0])
    return out
randomized: list = [randint(0, 1000) for x in range(10000)]
clone = [x for x in randomized]
assert sorted(clone) == merge_sort(randomized)

package main
import (
    "fmt"
)
func main() {
    A := []int{3, 5, 1, 6, 1, 7, 2, 4, 5}
    fmt.Println(sort(A))
}
// top-down approach
func sort(A []int) []int {
    if len(A) <= 1 {
        return A
    }
    left, right := split(A)
    left = sort(left)
    right = sort(right)
    return merge(left, right)
}
// split array into two
func split(A []int) ([]int, []int) {
    return A[0:len(A) / 2], A[len(A) / 2:]
}
// assumes that A and B are sorted
func merge(A, B []int) []int {
    arr := make([]int, len(A) + len(B))
    // index j for A, k for B
    j, k := 0, 0
    for i := 0; i < len(arr); i++ {
        // fix for index out of range without using sentinel
        if j >= len(A) {
            arr[i] = B[k]
            k++
            continue
        } else if k >= len(B) {
            arr[i] = A[j]
            j++
            continue
        }
        // default loop condition
        if A[j] > B[k] {
            arr[i] = B[k]
            k++
        } else {
            arr[i] = A[j]
            j++
        }
    }
    return arr
}