merge_sort.c File Reference

Top-down merge sort with explicit auxiliary buffer. More...

#include "sorts.h"
#include <stdlib.h>
#include <string.h>

Go to the source code of this file.

Functions
static void	merge_int (int *arr, int *aux, size_t lo, size_t mid, size_t hi)
static void	merge_sort_int_recursive (int *arr, int *aux, size_t lo, size_t hi)
void	merge_sort_ints (int *arr, size_t n)
static void	merge_sort_str_recursive (char **arr, char **aux, size_t lo, size_t hi)
void	merge_sort_strings (char **arr, size_t n)
static void	merge_str (char **arr, char **aux, size_t lo, size_t mid, size_t hi)

Detailed Description

Top-down merge sort with explicit auxiliary buffer.

Stable, O(n log n) worst-case, O(n) extra space. The aux buffer is allocated once at the top-level call and reused for every merge to avoid per-recursion malloc churn.

Definition in file merge_sort.c.

Function Documentation

merge_int()

static void merge_int ( int *  arr, int *  aux, size_t  lo, size_t  mid, size_t  hi  )

static

Definition at line 46 of file merge_sort.c.

Referenced by merge_sort_int_recursive().

merge_sort_int_recursive()

static void merge_sort_int_recursive ( int *  arr, int *  aux, size_t  lo, size_t  hi  )

static

Definition at line 58 of file merge_sort.c.

References merge_int(), and merge_sort_int_recursive().

Referenced by merge_sort_int_recursive(), and merge_sort_ints().

merge_sort_ints()

void merge_sort_ints	(	int *	arr,
		size_t	n
	)

Definition at line 66 of file merge_sort.c.

References merge_sort_int_recursive().

merge_sort_str_recursive()

static void merge_sort_str_recursive ( char **  arr, char **  aux, size_t  lo, size_t  hi  )

static

Definition at line 28 of file merge_sort.c.

References merge_sort_str_recursive(), and merge_str().

Referenced by merge_sort_str_recursive(), and merge_sort_strings().

merge_sort_strings()

void merge_sort_strings	(	char **	arr,
		size_t	n
	)

Definition at line 36 of file merge_sort.c.

References merge_sort_str_recursive().

Referenced by algo_from_name().

merge_str()

static void merge_str ( char **  arr, char **  aux, size_t  lo, size_t  mid, size_t  hi  )

static

Definition at line 16 of file merge_sort.c.

Referenced by merge_sort_str_recursive().