[largorithm][mergesort] 머지소트 (C / Python)

C Language

main.c

#include 
#include 
#include "mergesort.h"

void printArray(int value[], int count);

int main()
{
    int values[] = { 80, 75, 10, 60, 15, 49, 12, 25 };
    int count = sizeof(values)/sizeof(int);

    mergesort(values, count);
    printArray(values, count);
    return 0;
}


void printArray(int value[], int count)
{
    int i = 0;
    for(i = 0; i < count; i++) {
        printf("%d ", value[i]);
    }
    printf("\n");
}

mergesort.h

#ifndef MERGESORT_H_INCLUDED
#define MERGESORT_H_INCLUDED

void mergesort(int* arr, int count);

#endif // MERGESORT_H_INCLUDED

mergesort_impl.c

#include 
#include 

#include "mergesort.h"

void _mergesort(int* arr, int* pBuffer, int start, int end);
void _mergesort_division(int* arr, int* pBuffer, int start, int middle, int end);

void mergesort(int* arr, int count)
{
    int* pBuffer = (int*)malloc(sizeof(int) * count);
    if(pBuffer != NULL)
    {
        _mergesort(arr, pBuffer, 0, 7);

        free(pBuffer);
    }
}

void _mergesort(int* arr, int* pBuffer, int start, int end)
{
    int middle = 0;
    if (start < end)
    {
        middle = (start + end) / 2;
        _mergesort(arr, pBuffer, start, middle);
        _mergesort(arr, pBuffer, middle+1, end);
        _mergesort_division(arr, pBuffer, start, middle, end);
    }
}

void _mergesort_division(int* arr, int* pBuffer, int start, int middle, int end)
{
    int i = 0, j = 0, k = 0, t = 0;
    i = start;
    j = middle + 1;
    k = start;

    while(i <= middle && j <= end)
    {
        if(arr[i] <= arr[j])
        {
            pBuffer[k] = arr[i];
            i++;
        }
        else
        {
            pBuffer[k] = arr[j];
            j++;
        }
        k++;
    }

    if(i <= middle)
    {
        for(t = i; t <= middle; t++, k++)
        {
           pBuffer[k] = arr[t];
        }
    }
    else
    {
        for(t = j; t <= end; t++, k++)
        {
            pBuffer[k] = arr[t];
        }
    }

    for (t = start; t <= end; t++)
    {
        arr[t] = pBuffer[t];
    }
}

Python

def merge_sort(arr):
    print('split', arr)
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        merge_sort(left)
        merge_sort(right)

        i, j, k = 0, 0, 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    print('merge', a)
a = [80, 75, 10, 60, 15, 49, 12, 25]
merge_sort(a)
print(a)