Talk:Insertion sort

improvement

This sample code is simple but is not efficient.

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        while j >= 0 and A[j] > value do
        begin
            A[j + 1] := A[j];
            j := j - 1;
        end;
        A[j + 1] := value;
    end;
end;

I would like to draw your attention to the end of for loop. 'A[j + 1]' is ALWAYS written back by 'value'. In addition, 'j' is also modified even insertion is not needed. This is waste of time.

In optimization-based point of view, 'j' is written by 'i - 1'; however, 'j' should be written by 'i'. 'j + 1' also should be replaced by 'j' and 'j' should be replaced by 'j - 1'. This change will help compilers to be able to generate good codes. 'j >= 0' is not needed in the first time.

Yaneurao shows an improved insertion sort implementation.

// yaneurao's insertion sort
for (int i = 1; i < MAX; i++) 
{
	int tmp = t[i];
	if (t[i-1] > tmp)
	{
		int j = i;
		do {
			t[j] = t[j-1];
			--j;
		} while ( j > 0 && t[j-1] > tmp);
		t[j] = tmp;
	}
}

This implementation will produce about 30% faster code than the original example.

Yaneurao says insertion sort is very useful when the size of array is small or the array is partially organized, therefore an improvement of insertion sort is very important. Surely, the original example is simple; however, it lacks essence of insertion sort. If you are not interested in performance, you can just use qsort which is usually provided by standard libraries.

You can find a similar sort code in famous Shogi program named Bonanza. That is, a insertion sort is often used by board game programs which need speed.

// Bonanza's descending order insertion sort
psortv[n] = INT_MIN; // put a delimiter in the last element.
for ( i = n-2; i >= 0; i-- )
{
	// If you regard 'sortv' and 'move' as 'tmp' variable
	// this is a normal insertion sort but loop variable moves descending order.
	sortv = psortv[i];  move = pmove[i];
	for ( j = i+1; psortv[j] > sortv; j++ )
	{
		// move one by one because of descending order
		psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
	}
	psortv[j-1] = sortv;  pmove[j-1] = move;
}

Bonanza's insertion sort code is not optimized enough; however, Bonanza's source code offers a useful example that typical insertion sort codes can be modified to descending order insertion sort codes and delimiter is used.

--59.146.253.157 (talk) 05:08, 28 November 2009 (UTC)

---I was also going to complain about this and other factors, a being it is not pseudocode, it is code. And unless you feel like looking up how to write Pascal it is almost incomprehensible(eg what is value? should be temp or something more explanatory), I guess the same can be said for the selection sort wiki page that has examples of java and c, however I know these two so not so bad for me, But I'm guessing others would have this problem. A nice "ENGLISH" like example should replace this code. eg.

  for each element in the array(traverse ascending)    do
  element i = 1
  temp = Array[i] 
  if Array[i - 1] > temp 
     element j = i
     do 
        Array[j] = Array[j-1] 
        j = j - 1
     while  j > 0 && Array[j-1] > temp
     Array[j] = temp
  end if
  i = i + 1

end for DONE

or something like that ^^ something more universal(preferably a bit better than my example), rather than a random language or additionally include examples for each of the top 10 languages. 124.171.188.197 (talk) 13:44, 7 December 2009 (UTC)

---

on the other hand I was still able to read and interpret, I just think these examples should not be included or if included then as english like as possible 124.171.188.197 (talk) 14:03, 7 December 2009 (UTC)

sort

Question: Which language is the example implementation written in?

The example is written in Python. I'm planning on simplifying it a bit, in particular to remove the cmp function being passed as a parameter:

• A built-in function cmp() already exists, and means something different (-ve if a<b, 0 if a=b, +ve if a>b);
• IMO, Python's lambda notation and default arguments are not appropriate for near pseudo-code;
• "a > b" is much better for trying to understand an algorithm than a function call.
• Custom Python types can define their own comparisons anyway, so a comparator parameter is unnecessary.

--Carey Evans

Could the example semi-pseudocode on the main page please be cleaned so that it looks like one language, rather than C with a dab of Eiffel? 193.203.149.227 18:34, 28 May 2007 (UTC)

Should heapsort be listed as type of insertion sort ? --Taw

No. Heapsort is more closely related to selection sort. --Damian Yerrick

Actually heapsort and insertion sort have a pretty close relation. In both, you are taking the elements of the list and successively inserting them into a data structure from which you can, at the end, extract the sorted sequence. In selection sort you actually search the unsorted elements; in these sorts you simply present the unsorted elements sequentially. Deco 05:54, 29 Mar 2005 (UTC)

Removed mergesort statement

I removed this statement:

This is even less than Merge sort for finite n, though both do O(n log n) comparisons.

Not only is this silly (you can't sort infinite lists in finite time, especially not with this sort) but it assumes that merge sort runs in exactly n log n time, rather than just Θ(n log n) time. The truth is that:

$\log n!=\log \prod _{i=1}^{n}i=\sum _{i=1}^{n}\log i.$

Now, we can bound it on both sides with integrals:

$n\log n-n+1=\int _{x=1}^{n}\log x<\sum _{i=1}^{n}\log i<\int _{x=1}^{n+1}\log x=(n+1)\log(n+1)-n$

So in fact log n! is $\Theta (n\log n)$, no different from mergesort (if we could somehow avoid the time for the swaps.) Deco 05:54, 29 Mar 2005 (UTC)

Erm...what? XreDuex (talk) 17:50, 13 March 2008 (UTC)

Implementations

I removed the following from the article, as most (if not all) are listed on the wikibook page. They can be added back if desired --DevastatorIIC 14:00, 31 May 2006 (UTC)

I've fixed the C example of insertionSort, now works properly without memory underflow, if the unsorted element shoul dbe inserted on the first position, the algorithm could insert the number on address *(array - 1).

Also i've changed the a[] variable for array[] for more readability. This example may be more suitable for understanding because no sub-functions are used.

17:35, 16 Sep 2006

DELETED THE IMPLIMENTATIONS FROM THE TALK PAGE ::

Since they've been deleted for more than a year, they're just clutter. Fresheneesz (talk) 09:43, 5 December 2007 (UTC)

More implementations

For some reason, people feel compelled to add implementations to this page. Here are some I just removed from the page:

c++ Example:

#include <iostream>
#include <cstdio>

//Originally Compiled tested with g++ on Linux
using namespace std;

bool swap(int&, int&); //Swaps Two Ints
void print_array(int* ar, int); //Nothing Just Shows The Array Visually
int ins_sort(int*, int); //The Insertion Sort Function

int main()
{
	int array[9] = {4, 3, 5, 1, 2, 0, 7, 9, 6}; //The Original Array
	desc(array, 9);
	*array = ins_sort(array, 9);
	cout << "Array Sorted Press Enter To Continue and See the Resultant Array" << endl
  	     << "-----------------8<-------------------------------->8--------------";
	getchar();
        desc(array, 9);
        getchar();
	return 0;
}
int ins_sort(int* array, int len)
{
	for (int i = 0; i < len; i++)
        {
		int val = array[i];
		int key = i;
		cout << "key(Key) = " << key << "\tval(Value) = " << val << endl;
		for (; key >= 1 && array[key-1] >= val; --key)
                {
			cout << "Swapping Backward\tfrom (key) " << key << " of (Value) " << array[key] << "\tto (key) " << key-1
                             << " of (Value) " << array[key-1];
			cout << "\n\t" << key << " <----> " << key-1 << "\t( " << array[key] << "<----> " << array[key-1] << " )";
			swap(array[key], array[key-1]);
			desc(array, 9);
		}
	}
	return *array;
}
bool swap(int& pos1, int& pos2)
{
	int tmp = pos1;
	pos1 = pos2;
	pos2 = tmp;
	return true;
}
void print_array(int* ar, int len)
{
	cout << endl << "Describing The Given Array" << endl;
	for (int i = 0; i < len; i++)
                cout << "_______" << "\t";
        cout << endl;
	for (int i = 0; i < len; i++)
                cout << " | " << i << " | " << "\t";
        cout << endl;
	for (int i = 0; i < len; i++)
                cout << " ( " << ar[i] << " ) " << "\t";
        cout<<endl;
	for (int i = 0; i < len; i++)
                cout << "-------" << "\t";
        getchar();
}

picture requires explanation

What does that "Example of insertion sort" show exactly? What do the x and y coordinates represent? Without this kind of explanation it isn't helpful at all! Fresheneesz (talk) 09:41, 5 December 2007 (UTC)

Removed claim about real-time apps

I removed this:

It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably.

This seems silly. Not only is it false, since caches could disrupt the running time of selection sort; if it's truly important to make insertion sort as uniformly slow as selection sort, one could always add delay loops or useless array accesses. --Doradus (talk) 17:58, 5 February 2008 (UTC)

No argument from me. The runtime of selection sort is more predictable, but for real-time applications it suffices to determine a reasonable upper bound on runtime, which can be done by sorting a reversed list, and my expectation is that insertion sort is faster in the worst case than selection sort is in the best case. Dcoetzee 20:35, 6 February 2008 (UTC)

insertion sort psudocode

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void insertionSort1(int *A, int length) {
	int i, j, value; /* This is from the psudocode */
	for (i = 1; i < length-1; i++) {
		value = A[i];
		j = i - 1;
		while (j >= 0 && A[j] > value) {
			A[j + 1] = A[j];
			j = j-1;
		}
		A[j+1] = value;
	}
}

void insertionSort2(int *A, int length) {
	int i, j, value; /* Corrected psudocode */
	for (i = 1; i < length; i++) {
		value = A[i];
		j = i - 1;
		while (j >= 0 && A[j] > value) {
			A[j + 1] = A[j];
			j = j-1;
		}
		A[j+1] = value;
	}
}

int main() {
	int length = 10;
	int array1[length];
	int array2[length];
	int i;
	srand(time(NULL));
	printf("Original array:\n");
	for (i = 0; i < length; i++) {
		array1[i] = array2[i] = random() % (2 * length);
		printf("\tarray[%d]: %d\n", i, array1[i]);
	}
	insertionSort1(array1, length);
	insertionSort2(array2, length);
	printf("Output of insertion sort 1 (from psudocode):\n");
	for (i = 0; i < length; i++)
		printf("\tarray1[%d] = %d\n", i, array1[i]);
	printf("Output of insertion sort 2 (corrected psudocode):\n");
	for (i = 0; i < length; i++)
		printf("\tarray2[%d] = %d\n", i, array2[i]);
	return 0;
}

/* OUTPUT: 
Original array:
        array[0]: 1
        array[1]: 16
        array[2]: 19
        array[3]: 5
        array[4]: 12
        array[5]: 4
        array[6]: 17
        array[7]: 10
        array[8]: 11
        array[9]: 13
Output of insertion sort 1 (from psudocode):
        array1[0] = 1
        array1[1] = 4
        array1[2] = 5
        array1[3] = 10
        array1[4] = 11
        array1[5] = 12
        array1[6] = 16
        array1[7] = 17
        array1[8] = 19
        array1[9] = 13
Output of insertion sort 2 (corrected psudocode):
        array2[0] = 1
        array2[1] = 4
        array2[2] = 5
        array2[3] = 10
        array2[4] = 11
        array2[5] = 12
        array2[6] = 13
        array2[7] = 16
        array2[8] = 17
        array2[9] = 19
*/

I do understand that the psudocode is zero-indexed (despite the i = 1 in the loop), however if you look closely at the code, A[length-1] (the last element in the array) will never be touched, much less sorted. —Preceding unsigned comment added by Jordanbray (talk • contribs) 19:00, 16 February 2008 (UTC)

It looks to me like the original worked fine and the revision is broken. Please can you double-check? OoS (talk) 18:47, 17 February 2008 (UTC)

Yes, the revision is broken. On the final pass through the outer loop, i=length(A) followed by value=A[i] generates an array index out of bounds exception. Silly rabbit (talk) 19:29, 17 February 2008 (UTC)

I think Jordan does not understand that the pseudocode notation "for i = 1 to length(A)-1" includes length(A)-1. The problem is in how the pseudocode was translated into the C code above, not in the pseudocode itself. Silly rabbit (talk) 19:32, 17 February 2008 (UTC)

Pseudocode fix

Implemented the pseudocode in Java today (Eclipse is my SDK). It does not sort the last index. Removing the -1 after array.length[A] (or length[A] if you prefer the pseudocode) sorts the last variable and does not throw an exception. I haven't traced the code yet to find out why, but I figured I'd fix the implementation on the article first. XreDuex (talk) 18:12, 13 March 2008 (UTC)

Please see the discussion of the preceding section. In the last loop, setting value = A[length(A)] will give an index out of bounds exception. It's likely that your Java implementation made the same error as the C implementation given above. I have reverted your erroneous correction to the pseudocode. silly rabbit (talk) 18:23, 13 March 2008 (UTC)

Instead of correcting a supposed "erroneous" error, you could try implementing it in Eclipse. No exception is thrown with or without the -1 after array.length, but with it the final index is not sorted. It also seems as if you don't understand which "-1" I am referring to (although my crappy wording in my original post probably didn't help). I am talking about the "-1" in the for loop's conditions.

public static void insSort(int[] a)
{
	for (int count = 1; count < a.length; count++)
	{
		int value = a[count];
		int temp = count-1;
		while (temp >= 0 && a[temp] > value)
		{
			a[temp + 1] = a[temp];
			temp = temp-1;
		}
		a[temp+1] = value;
	}
}

I also do not see how the discussion on the C implentation is relevant at all, as no error results. XreDuex (talk) 17:54, 14 March 2008 (UTC)

He's right - you did make the same error as the C program above. The upper bound in the pseudocode is inclusive, while the upper bound in your for loop is exclusive. This requires an adjustment of the loop bound by 1. I suppose the pseudocode could be clarified, but this is a minor detail that would distract from the topic at hand if given too much attention. Dcoetzee 00:31, 15 March 2008 (UTC)

Code block templates

Hi all. A while ago I began an experiment with a new method for discouraging incorrect good-faith changes to code and pseudocode called "code block templates" on the articles quicksort and binary search algorithm. So far there haven't been any incorrect new changes to those code block templates, but very few changes have been made, so I'd like to expand the scope of this experiment to see how effective it is. This is one of the articles I'm targeting for this second phase. Please let me know on my talk page if you have any questions or concerns. Thanks! Dcoetzee 21:37, 7 December 2008 (UTC)

The C++ code is broken. Try sorting a list of length 1. You will get index-out-of-bounds error. —Preceding unsigned comment added by 207.67.97.194 (talk) 13:30, 13 August 2009 (UTC)

Linked Lists and O(n log n)

In college I was taught to use insertion sort on Linked Lists, not on arrays. A static array does indeed require that you shift all the existing elements down in order to make room for the new inserted item. Using doubly linked lists does not require a shift to make room. The item is actually inserted into your growing sorted list. After all insertions are performed you delete the old list out of memory. This type of algorithm actually gives you a O(n log n) time. Before I came to this article, I was totally unaware that Insertion Sorts were ever used on arrays, as this seems hopelessly cumbersome to me. paros (talk) 07:09, 20 December 2008 (UTC)

To the contrary, it has similar performance on linked lists, because it still requires linear time to find the correct place in the list in which to insert each new item. This variant uses less writes, but the same number of reads and comparisons. You could build a binary tree on top of the linked list, but then you're talking about binary tree sort. Dcoetzee 07:26, 20 December 2008 (UTC)

An example to use?

Personally I've been confused on how the Insertion Sort works, and I found a website that explained it well with an example. Insertion Sort example

Here is the example used on the website:

5|7034261(0)
57|034261(0)
057|34261(2)
0357|4261(2)
03457|261(2)
023457|61(4)
0234567|1(1)
01234567|(6)

Avaviel (talk) 16:51, 18 March 2009 (UTC)

Pseudocode bug

10 Oct 2009: I think the for-loop in the pseudo-code is wrong: If the array is zero-based and the for-loop includes the top index (as stated above the pseudo code), the access to A[i] goes beyond the upper bound of the array in the last execution of the loop. The third line should be

for i := 1 to length[A]-1 do

4 Nov 2009: I agree with the above remark. —Preceding unsigned comment added by 193.32.3.83 (talk) 11:14, 4 November 2009 (UTC)

11 Nov 2009: Yes, the pseudo-code definitely needs fixing. —Preceding unsigned comment added by 89.132.46.212 (talk) 08:52, 11 November 2009 (UTC)

What does running time in this context mean?

In the listing of the advantages of insertion sort, it says that the average running time is n²/4. I thought running time was measured in seconds, or have I missed anything? How does this notation better describe the behaviour of the algorithm than normal ordo (big O) notation? If this actually is the average number of comparisons of elements, or swaps or anything, I think the article should say that instead of using the somewhat misleading expression running time. --Kri (talk) 21:41, 28 November 2009 (UTC)

I agree - it most likely is referring here to comparisons, or comparisons plus exchanges, but we really need a proper reference for this. Dcoetzee 07:53, 29 November 2009 (UTC)

Pseudocode problem

I have a conceptual problem with the pseudocode. Let me give some background first. This is a bit long, so please bear with me :-)

I need to use Insertion sort in VBScript. I initially expected to perform a non-trivial translation, of the pseudocode, into VBScript. However, I soon realized that the translation is quite trivial.

VBScript already has 0-based arrays, and endpoint-inclusive FOR loops. I had to change the pseudocode WHILE DO WEND, into a VBScript DO WHILE LOOP, but those two constructs have precisely the same semantics. The only other changes were trivial syntax changes such as := to =, and [] to ().

Here's the result:

SUB INSERTION_SORT (A)
dim i, j, value
    for i = 1 to ubound (A)
        value = A (i)
        j = i - 1
        DO while j >= 0 and A (j) > value
            A (j + 1) = A (j)
            j = j - 1
        LOOP
        A (j + 1) = value
    next
END SUB

This code dies immediately with an array bounds error. I initially thought that I'd copied it wrongly. However, the problem is in the WHILE expression 'j>=0 and A(j)>value'. VBScript does not "short circuit" boolean expressions when it evaluates them. So it always tries to evaluate A(j), even when j<0. This is an array bounds error, and VBScript quite rightly complains.

So what?

I fully understand that there is a difference between (a) the pseudocode describing an algorithym, and (b) an implementation of that pseudocde in some particular programming language. Clearly, a developer can introduce errors when producing (b) from (a). That's his fault, you can't blame (a) for that.

However, in this example, I'm effectively "running the pseudocode itself, directly in VBScript" - and it does not work! I can't see this as anything other-than a deficiency in the pseudocode. The VBScript implementation has exposed the fact that the pseudocode performs an illogical operation, namely, testing an array element that does not exist.

You could say: "But the pseudocode assumes short-circuit expression evaluation!". I'd reply: "Who says? How would any reader know that? Short-circuiting is an implementation language issue. Why is such an issue relied-on in the pseudocode? That's the tail, wagging the dog!"

The real problem

The pseudocode expresses the requirement wrongly. Logically, the actual requirement is to FIRST check if j<0, THEN, if and only if it isn't, check the value of A[j]. The pseudocode incorrectly suggests that you can do both checks at the same time. That is simply not correct from a logical viewpoint.

This exact problem is a very common programming problem. Different people solve it differently. Some people use flags. Some add extra tests inside the loop. And others use short-circuiting, if supported by the language in question. Some of those methods are language neutral, eg. flags and extra tests, while others are clearly language specific, eg. short-circuiting.

IMHO, language neutral pseudocode should not assume behaviour, like short-circuiting, that is clearly language specific.

In language neutral pseudocode, you can reasonably assume that 'FOR N=1 TO 10' will go from 1 to 10 inclusive. But in 'N=0 AND BLAH', you can't reasonably assume that BLAH is only referenced when N=0. That assumes short-circuiting!

What to do about this?

I believe that we should fix it. I can see four ways to do so.

(1) Create a new pseudocode construct that seperates the two tests in question. I've shown a possible way below. Sorry for the funky markup, I can't get proper markup working inside the PRE block, for some reason.

        while j >= 0 and A[j] > value do
              ^^DELETE^^
        begin
            A[j + 1] := A[j];
            j := j - 1;
        end until j < 0;
            ^^^^ADD^^^^

Pros: Does not rely on short circuiting. j is always >=0 on entry to the loop, so the reference to A[j] at the top will always work first time. Then the test at the bottom kills the loop as soon as j goes <0, before it returns to the top and tests A[j] again.

Cons: Probably not as clear as I originally thought. :-(

(2) Alternativey, change the loop as follows:

        while j >= 0 and A[j] > value do
              ^^DELETE^^
        begin
            A[j + 1] := A[j];
            j := j - 1;
            if j < 0 then exit while;  <<<< ADD <<<<
        end;

Pros: Easy to understand. ("The instant j goes <0, get outta there fast!")

Cons: The implementation language might not let you exit WHILE loops prematurely. But this is the sort of problem that you always face when implementing pseudocode. It's the implementor's problem to work out how to get the right result in the implementation language used.

(3) Use a short-circuit operator, eg. the && from C-style languages:

        while j >= 0  &&  A[j] > value do
                     ^^^^
        begin
            A[j + 1] := A[j];
            j := j - 1;
        end;

Pros: Clearly the simplest and most elegant solution - for readers who understand what && means.

Cons: There would be many readers who do not know what && means. It's a language specific operator, so I question whether it should be used in language-neutral pseudocode. If it were to be used, it should be hyperlinked directly to an explanation of what it does. If a reader didn't understand it, but couldn't be bothered to click it to see, that would be their problem.

(4) At the very least, we should add a note explaining all this. For example: "Note: the following test assumes that if j<0 then the loop will terminate immediately, without referencing A[j]. In languages where that doesn't occur, the test might fail with an array bounds error, when it tries to access A[-1]." But who wants all that guff in the middle of the pseudocode? Its very presence screams: "There is something wrong with this!"

Recommendations

(A) The existing pseudocode has an inappropriate assumption that expressions are short-circuited. I recommend that we fix this using one of the four solutions above.

(B) The referenced article: http://en.wikipedia.org/wiki/Pseudocode does not refer to short-circuiting. This is relevant to pseudocode, so it should be mentioned there.

What says the borg?

PS. I got a logon message (earlier today, perhaps from a different IP?) chastising me for vandalizing an article on a highschool somewhere. I work from public internet, that was nothing to do with me!

TC 203.122.223.121 (talk) 10:28, 18 January 2010 (UTC)

I'm surprised that no-one has a view on this. I'm away for a few days. If there are no comments (pro or con) when I return, I'll assume that no-one cares one way or the other, and will amend the pseudocode using option (2) above. TC 203.122.223.121 (talk) 03:48, 21 January 2010 (UTC)

Done. TC 203.122.223.121 (talk) 10:33, 24 January 2010 (UTC)

It's worth noting that some languages offer a clearly distinguishing, short-circuiting form of its boolean operators (this is usually true when the default form is not short-circuiting). For example, Ada has operators "and then" and "or else", while VB.NET adds "AndAlso"/"OrElse" - both with names clearly implying short-circuiting. That said, an explicit conditional is clearer still. On the other hand, "exit while" is itself a "BASICism", and is generally frowned upon in pseudocode, where boolean flags are preferred over goto-like constructs (which early loop termination is). Especially since pseudocode is written is pretty much untyped Pascal, which never had anything like "exit while". So I'll change it to use a boolean flag instead. -- int19h (talk) 17:39, 4 February 2010 (UTC)

Personally I feel that makes it much less clear. And it would have been good to discuss it here first: like I did! But whatever... 203.122.223.121 (talk) 04:14, 8 February 2010 (UTC)

Python Source Example

Changed the use of range() to xrange() for efficiency. The range() function creates a list with every element between 1 and N, xrange() only stores the current value and when called for the next value it increments the stored value and yields it. xrange() is the correct function to use here unless you like adding N to the cost of your implementation. Asdquefty (talk) 00:20, 11 April 2010 (UTC)

I've changed the Python example to be more similar to the Pascal code because I had to look at both to understand the algorithm, and the Python variable names are confusing. Asdquefty (talk) 00:38, 11 April 2010 (UTC)

Pascal is not Pseudocode

Pascal is not pseudocode, it includes too many language-specific statements that don't mean anything to you unless you're the pascal compiler. Do you see "do", "begin", and "end" shoved in random places when you read an instruction manual? Of course not, it doesn't make sense, and most people find instructions hard enough to read as it is. Asdquefty (talk) 00:43, 11 April 2010 (UTC)

More productively, one could refer to the page on Shell sort where there is a good example of how pseudocode should be written. Asdquefty (talk) 04:02, 12 April 2010 (UTC)

I agree - the existing code is confusing. It is also marked as pascal in the markup whereas the text says it is pseudocode. It can't be both. I would suggest:

insertionSort(array A)
begin
   for i := 1 to length[A]-1 do
   begin
       value := A[i];
       j := i - 1;
       while j >= 0 and A[j] > value do
       begin
           A[j + 1] := A[j];
           j := j - 1;
       end
       A[j + 1] := value;
   end;
end;

Danio (talk) 16:00, 4 May 2010 (UTC)

What you wrote above is still very similar to Pascal. While it is more concise, I think the begin/end statements distract the reader from the intent of the pseudocode. At the least, I feel it is redundant to have "do" and "begin" to denote the start of a loop block, pick one or the other. I suggest:

insertionSort(array A)
begin
   for i := 1 to length[A]-1
   do
       value := A[i];
       j := i - 1;
       while j >= 0 and A[j] > value
       do
           A[j + 1] := A[j];
           j := j - 1;
       end
       A[j + 1] := value;
   end;
end;

Personally, I find pseudocode much more readable when it is written to resemble Python, not Pascal, since Python code was designed to get to the point without redundant statements. Asdquefty (talk) 19:33, 4 May 2010 (UTC)

Animation is useless

In the "Best, worst, and average cases", the animation is utterly useless; it does not prove anything . It does not even clearly resemble any kind of sorting algorithm. I strongly suggest for it to be removed. 70.24.154.237 (talk) 00:59, 4 May 2010 (UTC)