Algorithm Speed (2.00) :

Array Size (100) :

Flash Sort :

Author(s) : Karl-Dietrich Neubert Date : 1998

Flash sort is a hybrid sorting algorithm that combines the strengths of radix sort and partitioning. It works by creating multiple partitions based on a sample of the input data. Elements are then distributed into these partitions using counting sort. Finally, each partition is sorted individually using insertion sort. Flash sort is known for its efficiency in specific scenarios and is sometimes used in specialized sorting libraries. However, its complexity depends on factors like the chosen sample size and the distribution of the input data.

Time Complexity	O(n + r)
Best Case	O(n)
Worst Case	O(n²)
Space Complexity	O(n)
Stable	No

import math

def flashsort(arr):
	n=len(arr)
	if n<=1:
		return arr

	max_val,min_val=max(arr),min(arr)

	range_val=max_val-min_val
	if range_val==0:
		return arr
	c=int(math.ceil(math.log(n,2)))
	m=int(n/c)

	dist=[0]*m

	for i in range(n):
		bucket=int(m*(arr[i]-min_val)/range_val)
		dist[bucket]+=1

	for i in range(1,m):
		dist[i]+=dist[i-1]

	c_ptr=[0]*m
	for i in range(n):
		bucket=int(m*(arr[i]-min_val)/range_val)
		c_ptr[bucket]-=1
		temp=arr[i]
		arr[dist[bucket]+c_ptr[bucket]]=temp

	for i in range(m-1):
		start=dist[i]
		end=dist[i+1]
		for j in range(start+1,end):
			temp=arr[j]
			k=j-1
			while k>=start and arr[k]>temp:
				arr[k+1]=arr[k]
				k-=1
			arr[k+1]=temp

	return arr

function flashsort(arr) {
	let n = arr.length;
	if (n <= 1) {
		return arr;
	}

	let maxVal = Math.max(...arr);
	let minVal = Math.min(...arr);

	let rangeVal = maxVal - minVal;
	if (rangeVal === 0) {
		return arr;
	}
	let c = Math.ceil(Math.log2(n));
	let m = Math.floor(n / c);

	let dist = new Array(m).fill(0);

	for (let i = 0; i < n; i++) {
		let bucket = Math.floor(m * (arr[i] - minVal) / rangeVal);
		dist[bucket]++;
	}

	for (let i = 1; i < m; i++) {
		dist[i] += dist[i - 1];
	}

	let cPtr = new Array(m).fill(0);
	for (let i = 0; i < n; i++) {
		let bucket = Math.floor(m * (arr[i] - minVal) / rangeVal);
		cPtr[bucket]--;
		let temp = arr[i];
		arr[dist[bucket] + cPtr[bucket]] = temp;
	}

	for (let i = 0; i < m - 1; i++) {
		let start = dist[i];
		let end = dist[i + 1];
		for (let j = start + 1; j < end; j++) {
			let temp = arr[j];
			let k = j - 1;
			while (k >= start && arr[k] > temp) {
				arr[k + 1] = arr[k];
				k--;
			}
			arr[k + 1] = temp;
		}
	}

	return arr;
}

import java.util.Arrays;

public class FlashSort {
	public static void flashsort(int[] arr) {
		int n = arr.length;
		if (n <= 1) {
			return;
		}

		int maxVal = Arrays.stream(arr).max().getAsInt();
		int minVal = Arrays.stream(arr).min().getAsInt();

		int rangeVal = maxVal - minVal;
		if (rangeVal == 0) {
			return;
		}
		int c = (int) Math.ceil(Math.log(n) / Math.log(2));
		int m = n / c;

		int[] dist = new int[m];

		for (int i = 0; i < n; i++) {
			int bucket = (int) (m * (arr[i] - minVal) / rangeVal);
			dist[bucket]++;
		}

		for (int i = 1; i < m; i++) {
			dist[i] += dist[i - 1];
		}

		int[] cPtr = new int[m];
		for (int i = 0; i < n; i++) {
			int bucket = (int) (m * (arr[i] - minVal) / rangeVal);
			cPtr[bucket]--;
			int temp = arr[i];
			arr[dist[bucket] + cPtr[bucket]] = temp;
		}

		for (int i = 0; i < m - 1; i++) {
			int start = dist[i];
			int end = dist[i + 1];
			for (int j = start + 1; j < end; j++) {
				int temp = arr[j];
				int k = j - 1;
				while (k >= start && arr[k] > temp) {
					arr[k + 1] = arr[k];
					k--;
				}
				arr[k + 1] = temp;
			}
		}
	}
}

package main

import (
	"math"
	"sort"
)

func flashsort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	maxVal, minVal := arr[0], arr[0]
	for _, v := range arr {
		if v > maxVal {
			maxVal = v
		}
		if v < minVal {
			minVal = v
		}
	}

	rangeVal := maxVal - minVal
	if rangeVal == 0 {
		return arr
	}
	c := int(math.Ceil(math.Log2(float64(len(arr)))))
	m := len(arr) / c

	dist := make([]int, m)

	for _, v := range arr {
		bucket := int(float64(m) * float64(v-minVal) / float64(rangeVal))
		dist[bucket]++
	}

	for i := 1; i < m; i++ {
		dist[i] += dist[i-1]
	}

	cPtr := make([]int, m)
	for i, v := range arr {
		bucket := int(float64(m) * float64(v-minVal) / float64(rangeVal))
		cPtr[bucket]--
		arr[dist[bucket]+cPtr[bucket]] = v
	}

	for i := 0; i < m-1; i++ {
		start := dist[i]
		end := dist[i+1]
		sort.Ints(arr[start:end])
	}

	return arr
}

#include <stdio.h>
#include <math.h>

void flashsort(int arr[], int n) {
	if (n <= 1) {
		return;
	}

	int maxVal = arr[0], minVal = arr[0];
	for (int i = 1; i < n; i++) {
		if (arr[i] > maxVal) {
			maxVal = arr[i];
		}
		if (arr[i] < minVal) {
			minVal = arr[i];
		}
	}

	int rangeVal = maxVal - minVal;
	if (rangeVal == 0) {
		return;
	}
	int c = (int) ceil(log2(n));
	int m = n / c;

	int dist[m] = {0};

	for (int i = 0; i < n; i++) {
		int bucket = (int) (m * (arr[i] - minVal) / rangeVal);
		dist[bucket]++;
	}

	for (int i = 1; i < m; i++) {
		dist[i] += dist[i - 1];
	}

	int cPtr[m] = {0};
	for (int i = 0; i < n; i++) {
		int bucket = (int) (m * (arr[i] - minVal) / rangeVal);
		cPtr[bucket]--;
		int temp = arr[i];
		arr[dist[bucket] + cPtr[bucket]] = temp;
	}

	for (int i = 0; i < m - 1; i++) {
		int start = dist[i];
		int end = dist[i + 1];
		for (int j = start + 1; j < end; j++) {
			int temp = arr[j];
			int k = j - 1;
			while (k >= start && arr[k] > temp) {
				arr[k + 1] = arr[k];
				k--;
			}
			arr[k + 1] = temp;
		}
	}
}