Algorithm Speed (2.00) :

Array Size (100) :

Spaghetti Sort :

Author(s) : A. K. Dewdney Date : 1984

Spaghetti sort is a linear-time, analog algorithm for sorting a sequence of items, introduced by A. K. Dewdney. It requires a parallel processor or a physical analog device to achieve its O(n) time complexity. In software, it is simulated by finding the maximum element and removing it, which takes O(n²) time.

Time Complexity	O(n²)
Best Case	O(n²)
Worst Case	O(n²)
Space Complexity	O(n)
Stable	Yes

def spaghetti_sort(arr):
	max_val = max(arr)
	poles = [0] * (max_val + 1)
	for num in arr:
		poles[num] += 1
	res = []
	for i in range(len(poles)):
		while poles[i] > 0:
			res.append(i)
			poles[i] -= 1
	return res

function spaghettiSort(arr) {
	let max = Math.max(...arr);
	let poles = new Array(max + 1).fill(0);
	for (let i = 0; i < arr.length; i++) {
		poles[arr[i]]++;
	}
	let res = [];
	for (let i = 0; i < poles.length; i++) {
		while (poles[i] > 0) {
			res.push(i);
			poles[i]--;
		}
	}
	return res;
}

public static int[] spaghettiSort(int[] arr) {
	int max = arr[0];
	for (int i = 1; i < arr.length; i++) {
		if (arr[i] > max) max = arr[i];
	}
	int[] poles = new int[max + 1];
	for (int i = 0; i < arr.length; i++) {
		poles[arr[i]]++;
	}
	int[] res = new int[arr.length];
	int index = 0;
	for (int i = 0; i < poles.length; i++) {
		while (poles[i] > 0) {
			res[index++] = i;
			poles[i]--;
		}
	}
	return res;
}

func spaghettiSort(arr []int) []int {
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
	}
	poles := make([]int, max+1)
	for _, v := range arr {
		poles[v]++
	}
	res := make([]int, 0, len(arr))
	for i, count := range poles {
		for count > 0 {
			res = append(res, i)
			count--
		}
	}
	return res
}

void spaghettiSort(int arr[], int n) {
	int max = arr[0];
	for (int i = 1; i < n; i++) {
		if (arr[i] > max) max = arr[i];
	}
	int *poles = (int *)calloc(max + 1, sizeof(int));
	for (int i = 0; i < n; i++) {
		poles[arr[i]]++;
	}
	int index = 0;
	for (int i = 0; i <= max; i++) {
		while (poles[i] > 0) {
			arr[index++] = i;
			poles[i]--;
		}
	}
	free(poles);
}