Strand Sort

// C program
// Strand Sort
#include <stdio.h>

#include <stdlib.h>

struct Node
{
	int element;
	struct Node *next;
};
//Create a node 
struct Node *create_node(int data)
{
	struct Node *node = (struct Node *) malloc(sizeof(struct Node *));
	if (node != NULL)
	{
		node->element = data;
		node->next = NULL;
	}
	return node;
}
//Merge two sorted list and return its result
struct Node *merge_list(struct Node *list1, struct Node *list2)
{
	if (list1 == NULL)
	{
		//When list1 is empty
		return list2;
	}
	else if (list2 == NULL)
	{
		return list1;
	}
	else
	{
		//Some auxiliary variables
		struct Node *head = NULL;
		struct Node *tail = NULL;
		struct Node *node = NULL;
		// Combine list elements in sorted order
		// This process takes(m+n) time
		// Here m is size of list1
		// And n is size of list2
		while (list1 != NULL || list2 != NULL)
		{
			if (list1 != NULL && list2 != NULL)
			{
				if (list1->element < list2->element)
				{
					node = list1;
					list1 = list1->next;
				}
				else
				{
					node = list2;
					list2 = list2->next;
				}
			}
			else if (list1 != NULL)
			{
				node = list1;
				list1 = list1->next;
			}
			else
			{
				node = list2;
				list2 = list2->next;
			}
			if (head == NULL)
			{
				//When get first node of resultant list
				head = node;
			}
			else
			{
				//Add node at end of resultant list
				tail->next = node;
			}
			node->next = NULL;
			tail = node;
		}
		return head;
	}
}
//Perform the standard sort of given list elements
struct Node *stander_sort(struct Node *input_list, struct Node *output_list)
{
	if (input_list == NULL)
	{
		return output_list;
	}
	//create new list and set first element of input list
	struct Node *sub_list = input_list;
	struct Node *tail = sub_list;
	struct Node *back = NULL;
	//visit to next element 
	//like remove first node initial input list
	input_list = sub_list->next;
	struct Node *auxiliary_list = input_list;
	int item = sub_list->element;
	while (auxiliary_list != NULL)
	{
		if (auxiliary_list->element > item)
		{
			//Add node at end of sublist
			tail->next = auxiliary_list;
			item = auxiliary_list->element;
			if (back == NULL)
			{
				//remove front node in actual list
				input_list = auxiliary_list->next;
				auxiliary_list = auxiliary_list->next;
			}
			else
			{
				auxiliary_list = auxiliary_list->next;
				//remove intermediate element
				back->next = auxiliary_list;
			}
			tail = tail->next;
		}
		else
		{
			back = auxiliary_list;
			auxiliary_list = auxiliary_list->next;
		}
	}
	// Separate the new sublist
	tail->next = NULL;
	output_list = merge_list(output_list, sub_list);
	return stander_sort(input_list, output_list);
}
//This are providing the environment setup to perform standard sort
void sort_element(int collection[], int size)
{
	if (size <= 1)
	{
		return;
	}
	//Loop controlling variable
	int i = 0;
	//Create editable list
	struct Node *input_list = NULL;
	struct Node *output_list = NULL;
	//Some auxiliary variables
	struct Node *tail = NULL;
	struct Node *node = NULL;
	//Find add array element into custom list
	for (i = 0; i < size; ++i)
	{
		node = create_node(collection[i]);
		if (input_list == NULL)
		{
			input_list = node;
		}
		else
		{
			tail->next = node;
		}
		tail = node;
	}
	output_list = stander_sort(input_list, output_list);
	input_list = NULL;
	i = 0;
	// Insert element into actual collection
	while (output_list != NULL)
	{
		//Get current node
		node = output_list;
		//set element into collection
		collection[i] = node->element;
		//visit to next node
		output_list = node->next;
		//free node
		free(node);
		node = NULL;
		i++;
	}
}
//Display element of given collection
void display_element(int collection[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", collection[i]);
	}
	printf("\n");
}
int main()
{
	// Define the unsorted array elements
	int collection[] = {
		7 , 3 , 0 , 8 , 23 , 2 , 9 , 35 , 13 , 12 , 1 , 3
	};
	//Get the size of given collection
	int size = sizeof(collection) / sizeof(collection[0]);
	printf("\n Before sort : ");
	display_element(collection, size);
	sort_element(collection, size);
	printf("\n After sort  : ");
	display_element(collection, size);
	return 0;
}

Output

 Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

 After sort  :   0  1  2  3  3  7  8  9  12  13  23  35