Algorithm Speed (2.00) :

Array Size (100) :

Insertion Sort :

Author(s) : Unknown Date : Ancient

Insertion sort iterates through the input array, considering each element from the second one onwards. It takes this element and inserts it into its correct position within the sub-array already considered to be sorted. This insertion is achieved by shifting larger elements in the sub-array one position to the right, creating a space for the element being inserted. Insertion sort is efficient for small arrays or partially sorted data (where many elements are already in their correct positions). However, its time complexity of O(n^2) in the worst case becomes a disadvantage for large datasets.

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

def insertionsort(arr):
	n = len(arr)
	for i in range(1, n):
		# Current element to be inserted
		key = arr[i]
		# Move elements, that are greater than key, to one position ahead
		j = i - 1
		while j >= 0 and key < arr[j]:
			arr[j + 1] = arr[j]
			j -= 1
		arr[j + 1] = key

# Test array
arr = [12, 11, 13, 5, 6, 7]
insertionsort(arr)
print('Sorted array is:', arr)

function insertionsort(arr) {
	let n = arr.length;
	for (let i = 1; i < n; i++) {
		// Current element to be inserted
		let key = arr[i];
		// Move elements, that are greater than key, to one position ahead
		let j = i - 1;
		while (j >= 0 && key < arr[j]) {
			arr[j + 1] = arr[j];
			j -= 1;
		}
		arr[j + 1] = key;
	}

	// Test array
	let arr = [12, 11, 13, 5, 6, 7];
	insertionsort(arr);
	console.log('Sorted array is:', arr);
}

public static void insertionsort(int[] arr) {
	int n = arr.length;
	for (int i = 1; i < n; ++i) {
		// Current element to be inserted
		int key = arr[i];
		// Move elements, that are greater than key, to one position ahead
		int j = i - 1;
		while (j >= 0 && key < arr[j]) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;
	}

	// Test array
	int[] arr = {12, 11, 13, 5, 6, 7};
	insertionsort(arr);
	System.out.println("Sorted array is:" + java.util.Arrays.toString(arr));
}

func insertionsort(arr []int) {
	n := len(arr)
	for i := 1; i < n; i++ {
		// Current element to be inserted
		key := arr[i]
		// Move elements, that are greater than key, to one position ahead
		j := i - 1
		for j >= 0 && key < arr[j] {
			arr[j + 1] = arr[j]
			j--
		}
		arr[j + 1] = key
	}

	// Test array
	arr := []int{12, 11, 13, 5, 6, 7}
	insertionsort(arr)
	fmt.Println("Sorted array is:", arr)
}

void insertionsort(int arr[], int n) {
	for (int i = 1; i < n; i++) {
		// Current element to be inserted
		int key = arr[i];
		// Move elements, that are greater than key, to one position ahead
		int j = i - 1;
		while (j >= 0 && key < arr[j]) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;
	}

	// Test array
	int arr[] = {12, 11, 13, 5, 6, 7};
	int n = sizeof(arr) / sizeof(arr[0]);
	insertionsort(arr, n);
	printf("Sorted array is: ");
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}