Merge Sort

from typing import List # For annotations

# Function to merge the sorted sub-arrays into a bigger array.
def Merge (aux_array : List[int], array : List[int], low : int, mid : int, high : int):

    left_index = low
    right_index = mid + 1
    aux_index = low

    # Merge elements from array[low : mid] and array[mid+1 : high]
    #                           ^                     ^
    #                           |                     |
    #                         left_index         right_index

    # Pick the smaller number between the left part and the right part
    while (left_index <= mid and right_index <= high):
        if (array[left_index] <= array[right_index]):
            aux_array[aux_index] = array[left_index]
            aux_index += 1
            left_index += 1
        else:
            aux_array[aux_index] = array[right_index]
            aux_index += 1
            right_index += 1

    if (left_index <= mid):
        # There are still some unpicked numbers in the left part
        for i in range(left_index, mid + 1):
            aux_array[aux_index] = array[i]
            aux_index += 1
    else:
        # There are still some unpicked numbers in the right part
        for i in range(right_index, high + 1):
            aux_array[aux_index] = array[i]
            aux_index += 1

    # Copy numbers from the sorted auxiliary array into the original array
    for i in range(low, high + 1):
        array[i] = aux_array[i]

# MergeSort function splits each sub-array till only a single element is available in the sub-array 
# and then proceeds with the merge of the sub-arrays into a bigger auxiliary array.
def MergeSort (aux_array : List[int], array : List[int], low : int, high : int):

    if (low < high):

       mid = int((low + high)/2)

       MergeSort (aux_array, array, low, mid)    # Recursively splits the left half of the array
       MergeSort (aux_array, array, mid+1, high) # Recursively splits the right half of the array

       Merge (aux_array, array, low, mid, high)  # Merge the left and the right half of the array keeping it sorted.

def main():

    array = [7, 3, 5, 2, 4, 1, 8, 6, 0, 10, 9]
    print("Unsorted array: " + str(array))

    # Allocate space for the auxiliary vector
    aux_array = [None] * len(array)

    MergeSort (aux_array, array, 0, len(array)-1)

    print("Sorted array using merge sort: " + str(array))

if __name__ == "__main__" :
    main()

Unsorted array: [7, 3, 5, 2, 4, 1, 8, 6, 0, 10, 9]
Sorted array using merge sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

#include<iostream>
#include<vector>

std :: vector<int> auxvec;

// Function to merge the sorted sub-arrays into a bigger array.
void Merge (std :: vector<int>& vec, int low, int mid, int high) {

    int left_index = low;
    int right_index = mid+1;
    int aux_index = low;

    /* Merge elements from vec[low : mid] and vec[mid+1 : high]
                                ^                  ^
                                |                  |
                              left_index       right_index    */

    // Pick the smaller number between the left part and the right part
    while (left_index <= mid and right_index <= high) {
       if (vec[left_index] <= vec[right_index]) {
          auxvec[aux_index++] = vec[left_index++];
       } else {
          auxvec[aux_index++] = vec[right_index++];
       }
    }

    if (left_index <= mid) {
       // There are still some unpicked numbers in the left part
       for (int i = left_index; i <= mid; i++) {
           auxvec[aux_index++] = vec[i];
       }
    } else {
       // There are still some unpicked numbers in the right part
       for (int i = right_index; i <= high; i++) {
           auxvec[aux_index++] = vec[i];
       }
    }

    // Copy numbers from the sorted auxiliary vector into the original vector
    for (int i=low; i<=high; i++) {
        vec[i] = auxvec[i];
    }
}

// MergeSort function splits each sub-array till only a single element is available in the sub-array 
// and then proceeds with the merge of the sub-arrays into a bigger auxiliary array.
void MergeSort (std :: vector<int>& vec, int low, int high) {

    int mid;
    if (low < high) {
       mid = (low + high)/2;
       MergeSort (vec, low, mid); // Recursively splits the left half of the array
       MergeSort (vec, mid+1, high); // Recursively splits the right half of the array
       Merge (vec, low, mid, high); // Merge the left and the right half of the array keeping it sorted.
    }
}

int main(){

    std :: vector<int> vec = {7, 3, 5, 2, 4, 1, 8, 6};
    // Allocate space for the auxiliary vector
    auxvec.resize(vec.size());
    MergeSort (vec, 0, vec.size()-1);

    std :: cout << "Sorted numbers : ";
    for (auto& it: vec)
        std :: cout << it << " ";
    return 0;
}

Sorted numbers : 1 2 3 4 5 6 7 8

class Sort {

    private int[] aux_array;

    // Allocate space to auxiliary array which is to be used for merging the sorted elements
    Sort (int sz) {
        aux_array = new int[sz];
    }

    // Function to merge the sorted sub-arrays into a bigger array.
    //void Merge (int[] aux_array, int[] array, int low, int mid, int high) {
    void Merge (int[] array, int low, int mid, int high) {

        int left_index = low;
        int right_index = mid+1;
        int aux_index = low;

        /* Merge elements from array[low : mid] and array[mid+1 : high]
                                      ^                     ^
                                      |                     |
                                  left_index         right_index */

        // Pick the smaller number between the left part and the right part
        while (left_index <= mid && right_index <= high) {
           if (array[left_index] <= array[right_index]) {
              aux_array[aux_index++] = array[left_index++];
           } else {
              aux_array[aux_index++] = array[right_index++];
           }
        }

        if (left_index <= mid) {
           // There are still some unpicked numbers in the left part
           for (int i = left_index; i <= mid; i++) {
               aux_array[aux_index++] = array[i];
           }
        } else {
           // There are still some unpicked numbers in the right part
           for (int i = right_index; i <= high; i++) {
               aux_array[aux_index++] = array[i];
           }
        }

        // Copy numbers from the sorted auxiliary array into the original array
        for (int i=low; i<=high; i++) {
            array[i] = aux_array[i];
        }
    }

    // MergeSort function splits each sub-array till only a single element is available in the sub-array 
    // and then proceeds with the merge of the sub-arrays into a bigger auxiliary array.
    //void MergeSort (int[] aux_array, int[] array, int low, int high) {
    void MergeSort (int[] array, int low, int high) {

        int mid;
        if (low < high) {
           mid = (low + high)/2;
           MergeSort (array, low, mid); // Recursively splits the left half of the array
           MergeSort (array, mid + 1, high); // Recursively splits the right half of the array
           Merge (array, low, mid, high); // Merge the left and the right half of the array keeping it sorted.
        }
    }

    public static void main (String[] args) {

        int[] array = {7, 3, 5, 2, 4, 1, 8, 6};
        //int[] aux_array = new int[array.length];

        System.out.print("Unsorted array: ");

        for (int i=0; i<array.length; i++)
            System.out.print(array[i] + " ");
        System.out.println();

        Sort s = new Sort(array.length);
        s.MergeSort (array, 0, array.length-1);

        System.out.print("Sorted array using Merge-Sort: ");

        for (int i=0; i<array.length; i++)
            System.out.print(array[i] + " ");
    }
}

Unsorted array: 7 3 5 2 4 1 8 6 
Sorted array using Merge-Sort: 1 2 3 4 5 6 7 8