Merge Sort

cpp_merge-sort.cpp

#include <iostream>
#include <vector>
using namespace std;

void merge(int l, int r, vector<int> &v) // Combina os resultados
{
    vector<int> S; // sequência auxiliar
    int mid = (l + r) / 2;
    int p1 = l;       // aponta para o primeiro elemento da parte 1
    int p2 = mid + 1; // aponta para o primeiro elemento da parte 2

    while (p1 <= mid && p2 <= r)
        if (v[p1] <= v[p2])
        {
            S.push_back(v[p1]);
            p1++;
        }
        else
        {
            S.push_back(v[p2]);
            p2++;
        }

    while (p1 <= mid) // Se ainda sobrarem elementos na parte 1
    {
        S.push_back(v[p1]);
        p1++;
    }

    while (p2 <= r) // Se ainda sobrarem elementos na parte 2
    {
        S.push_back(v[p2]);
        p2++;
    }

    for (int i = 0; i < S.size(); i++)
        v[l + i] = S[i];
    // agora, o intervalo [l, r] em v está ordenado
}

void mergeSort(int l, int r, vector<int> &v) // Divide o problema
{
    int mid;

    if (l < r)
    {
        mid = (l + r) / 2;
        mergeSort(l, mid, v);     // Ordena a parte 1
        mergeSort(mid + 1, r, v); // Ordena a parte 2
        merge(l, r, v);
    }
}

int main()
{
    vector<int> x = {9, 4, 2, 1, -3, 1, 7, 19, 32, 23, -17};
    int N = (int)x.size();

    mergeSort(0, N - 1, x);

    return 0;
}

py_merge-sort.py

def merge(l, r, v):
    S = []
    mid = (l+r) // 2
    p1 = l
    p2 = mid + 1

    while p1 <= mid and p2 <= r:
        if (v[p1] <= v[p2]):
            S.append(v[p1])
            p1 += 1
        else:
            S.append(v[p2])
            p2 += 1
    
    while p1 <= mid:
        S.append(v[p1])
        p1 += 1
    while p2 <= r:
        S.append(v[p2])
        p2 += 1
    
    for i in range(len(S)):
        v[l + i] = S[i]

def mergeSort(l, r, v):
    if (l < r):
        mid = (l+r) // 2
        mergeSort(l, mid, v)
        mergeSort(mid+1, r, v)
        merge(l, r, v)

def main():
    x = [9, 4, 2, 1, -3, 1, 7, 19, 32, 23, -17]
    N = len(x)

    mergeSort(0, N-1, x)

if __name__ == '__main__':
    main()