Make the frequent cases fast and the rare case correct

Insertion Sort (variant) of an Array using a Linked List

Insertion sort using a linked list is a variant as we can avoid having to make a series of swaps for each insertion, the input could be stored in a linked list, which allows elements to be inserted and deleted in constant-time.

Each element is copied from array to list and then back to array so there are 2N copies of elements but if we were to do insertion sort in place in the array then there would be N2 copies.

Although this variant reduces runtime with regards to copies, it is still a O(N2) algorithm as each item is inserted into the list and is compared with at least half the elements in the list already present with N items in total to insert.

In essence performing a binary search on a linked list is impractical because random access is not directly supported by a linked list and can only be effectively achieved by sequentially following the link chain to each desired element, which is relatively very slow; therefore, the running time required for searching is O(n2) – Wikipedia

so total run time = O(n2)[searching] + 2n [copies]

class Node
	public int item;
	public Node next;
	public Node(int val)
		item = val;
class InsSort
	private Node first;
	public InsSort()
	{ first = null; }
	public InsSort(Node[] linkArr)
		first = null;;
		for(int j=0; j<linkArr.length; j++)
			insert( linkArr[j] );
	public void insert(Node k)
		Node previous = null;
		Node current = first;
		while(current != null && k.item > current.item)
			previous = current;
			current =;
			first = k;
		else = k; = current;
	public Node pop()
		Node temp = first;
		first =;
		return temp;
class InsSortListBlog
	public static void main(String[] args)
		int size = 10;
		Node[] linkArray = new Node[size];
		for(int j=0; j<size; j++)
			int n = (int)(java.lang.Math.random()*99);
			Node newLink = new Node(n);
			linkArray[j] = newLink;
		System.out.print("Input unsorted array: ");
		for(int j=0; j<size; j++)
			System.out.print( linkArray[j].item + " " );
		InsSort theInsSort = new InsSort(linkArray);
		for(int j=0; j<size; j++)
			linkArray[j] = theInsSort.pop();
		System.out.print("sorted array: ");	
		for(int j=0; j<size; j++)
			System.out.print(linkArray[j].item + " ");


labuser@ubuntu:~/InsSortList$ java InsSortListBlog
Input unsorted array: 82 8 87 29 73 86 96 15 91 44
sorted array: 8 15 29 44 73 82 86 87 91 96

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: