1 files changed, 98 insertions, 0 deletions
diff --git a/libft/src/algo/ft_mergesort.c b/libft/src/algo/ft_mergesort.c
new file mode 100644
index 0000000..8556145
--- /dev/null
+++ b/libft/src/algo/ft_mergesort.c
@@ -0,0 +1,98 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_mergesort.c                                     :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/02/10 02:26:41 by cacharle          #+#    #+#             */
+/*   Updated: 2020/04/04 22:40:55 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+/*
+** \brief        Helper function to return in case of error
+** \param left   Left subarray
+** \param right  Right subarray
+** \return       -1 to indicate error
+*/
+
+static int	st_mergesort_error(void *left, void *right)
+{
+	free(left);
+	free(right);
+	return (-1);
+}
+
+/*
+** \brief         Merge 2 sorted arrays
+** \param arrays  Struct containing the arrays (base, left, right)
+** \param nel     Number of element in base
+** \param compar  Comparison function
+*/
+
+static void	st_merge_sorted(struct s_merge_sorted_arrays *arrays, size_t nel,
+				size_t width, int (*compar)(const void *, const void *))
+{
+	size_t	bi;
+	size_t	li;
+	size_t	ri;
+	size_t	mid;
+
+	mid = nel / 2;
+	bi = 0;
+	li = 0;
+	ri = 0;
+	while (li < mid && ri < nel - mid)
+	{
+		if (compar(arrays->left + li * width, arrays->right + ri * width) < 0)
+			ft_memcpy(arrays->base + bi * width,
+						arrays->left + li++ * width, width);
+		else
+			ft_memcpy(arrays->base + bi * width,
+						arrays->right + ri++ * width, width);
+		bi++;
+	}
+	while (li < mid)
+		ft_memcpy(arrays->base + bi++ * width,
+					arrays->left + li++ * width, width);
+	while (ri < nel - mid)
+		ft_memcpy(arrays->base + bi++ * width,
+					arrays->right + ri++ * width, width);
+}
+
+/*
+** \brief    Sort an array using the merge sort algorithm
+** \param base    Array to sort
+** \param nel     Number of element in the array
+** \param width   Size of each element
+** \return        0 on success, -1 on error
+*/
+
+int			ft_mergesort(void *base, size_t nel, size_t width,
+				int (*compar)(const void *, const void *))
+{
+	size_t							mid;
+	struct s_merge_sorted_arrays	arrays;
+
+	if (nel < 2)
+		return (0);
+	mid = nel / 2;
+	if ((arrays.left = malloc(mid * width)) == NULL)
+		return (-1);
+	if ((arrays.right = malloc((nel - mid) * width)) == NULL)
+		return (st_mergesort_error(arrays.left, NULL));
+	ft_memcpy(arrays.left, base, mid * width);
+	ft_memcpy(arrays.right, base + mid * width, (nel - mid) * width);
+	if (ft_mergesort(arrays.left, mid, width, compar) == -1)
+		return (st_mergesort_error(arrays.left, arrays.right));
+	if (ft_mergesort(arrays.right, nel - mid, width, compar) == -1)
+		return (st_mergesort_error(arrays.left, arrays.right));
+	arrays.base = base;
+	st_merge_sorted(&arrays, nel, width, compar);
+	free(arrays.left);
+	free(arrays.right);
+	return (0);
+}