# Interpolation Sort

Interpolation sort is an algorithm for sorting an array of values by inserting each element into its proper position within a sorted sublist of previously sorted elements. It is an extension of binary search to find the position where an element should be inserted.

The algorithm works by estimating the position of the element to be inserted, based on the range of values in the sorted sublist and the value of the element itself. This estimate is obtained using a formula that takes into account the minimum and maximum values in the sublist, as well as the position of the element relative to these values. The estimate is then used to perform a binary search on the sublist to find the correct position for the element.

Interpolation sort has an average case time complexity of O(n log n) and a worst case time complexity of O(n^2), which occurs when the input array is already sorted in reverse order. However, in practice, it tends to perform well on inputs that are already partially sorted, or have a fairly even distribution of values.

Overall, interpolation sort can be a useful sorting algorithm when dealing with certain types of input data, but its performance may not be as good as other sorting algorithms in some cases.

Here given code implementation process.

/*
Java program
Interpolation Sort
*/
import java.util.*;
public class Sorting
{
// Display elements of given sequence
public void display(int[] sequence, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("  " + sequence[i]);
}
System.out.print("\n");
}
// Sort elements using interpolation sort
public void interpolationSort(int[] sequence, int size)
{
if (size <= 0)
{
return;
}
int start = 0;
int end = size;
int location = 0;
int slot = 0;
// Loop controlling variables
int i = 0;
int j = 0;
// Define min max variable
int min = 0;
int max = 0;
ArrayList < Integer > process = new ArrayList < Integer > ();
ArrayList < ArrayList < Integer >> bucket = new ArrayList < ArrayList < Integer > > ();
// Assign the memory of each slot
for (i = 0; i < size; ++i)
{
// Allocate memory
bucket.add(new ArrayList < Integer > ());
}
// Add the size of array
while (process.size() > 0)
{
// Get last size
location = process.get(process.size() - 1);
// Remove the last element of process
process.remove(process.size() - 1);
// Get start location
start = end - location;
// Get starting element
max = sequence[start];
min = sequence[start];
// Find minimum and maximum
for (i = start + 1; i < end; i++)
{
if (sequence[i] > max)
{
max = sequence[i];
}
else if (sequence[i] < min)
{
min = sequence[i];
}
}
if (min == max)
{
// Change last element
end = end - location;
}
else
{
for (i = start; i < end; ++i)
{
// Calculate slot
slot = (int) Math.floor(((sequence[i] - min) / (double)(max - min)) * (location - 1));
}
for (i = 0; i < location; ++i)
{
if (bucket.get(i).isEmpty() == false)
{
// When bucket slot not empty
// Assign the bucket element into actual array
for (j = 0; j < bucket.get(i).size(); j++)
{
sequence[start] = bucket.get(i).get(j);
start++;
}
// This is useful to trace the sort slot elements
}
}
// Remove the existing bucket element
for (i = 0; i < size; ++i)
{
bucket.get(i).clear();
}
}
}
}
public static void main(String[] args)
{
// Define array of positive integer elements
int[] s1 = {
61 , 53 , 42 , 14 , 64 , 2 , -2 , 6 , 17 , 9 , 11 , 3 , 3 , 4 , 7
};
int[] s2 = {
16 , 12 , 6 , 2 , 8 , 5 , 9 , 3 , 5 , 21 , 22
};
// Test case A
int size = s1.length;
System.out.print("  Before Sort \n");
System.out.print("  After Sorted \n");
// Test case B
size = s2.length;
System.out.print("\n  Array \n");
System.out.print("  After Sorted \n");
}
}

#### Output

Before Sort
61  53  42  14  64  2  -2  6  17  9  11  3  3  4  7
After Sorted
-2  2  3  3  4  6  7  9  11  14  17  42  53  61  64

Array
16  12  6  2  8  5  9  3  5  21  22
After Sorted
2  3  5  5  6  8  9  12  16  21  22

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.