text:
Institute of National Remembrance

The Institute of National Remembrance – Commission for the Prosecution of Crimes against the Polish Nation (Instytut Pamięci Narodowej – Komisja Ścigania Zbrodni przeciwko Narodowi Polskiemu, abbreviated IPN) is a Polish state research institute in charge of education and archives which also includes two public prosecution service components exercising investigative, prosecution and lustration powers. The IPN was established by the Polish parliament by the Act on the Institute of National Remembrance of 18 December 1998 through reforming and expanding the earlier Main Commission for the Investigation of Crimes against the Polish Nation of 1991, which itself had replaced a body on Nazi crimes established in 1945.

In 2018, IPN's mission statement was amended by the controversial Amendment to the Act on the Institute of National Remembrance to include "protecting the reputation of the Republic of Poland and the Polish Nation". The IPN investigates and prosecutes Nazi and Communist crimes committed between 1917 and 1990, documents its findings, and disseminates them to the public. Some scholars have criticized the IPN for politicization, especially under Law and Justice governments.

The IPN began its activities on 1 July 2000. The IPN is a founding member of the Platform of European Memory and Conscience. Since 2020, the IPN headquarters have been located at Postępu 18 Street in Warsaw. The IPN has eleven branches in other cities and seven delegation offices.

Purpose
The IPN's main areas of activity, in line with its original mission statement, include researching and documenting the losses which were suffered by the Polish Nation as a result of World War II and during the post-war totalitarian period. The IPN informs about the patriotic traditions of resistance against the occupational forces, and the Polish citizens' fight for sovereignty of the nation, including their efforts in defence of freedom and human dignity in general.

According to the IPN, it is its duty to prosecute crimes against peace and humanity, as much as war crimes. Its mission includes the need to compensate for damages which were suffered by the repressed and harmed people at a time when human rights were disobeyed by the state, and educate the public about recent history of Poland. IPN collects, organises and archives all documents about the Polish Communist security apparatus active from 22 July 1944 to 31 December 1989.

Following the election of the Law and Justice party, the government formulated in 2016 a new IPN law. The 2016 law stipulated that the IPN should oppose publications of false information that dishonors or harms the Polish nation. It also called for popularizing history as part of "an element of patriotic education". The new law also removed the influence of academia and the judiciary on the IPN.

A 2018 amendment to the law, added article 55a that attempts to defend the "good name" of Poland. Initially conceived as a criminal offense (3 years of jail) with an exemption for arts and research, following an international outcry, the article was modified to a civil offense that may be tried in civil courts and the exemption was deleted. Defamation charges under the act may be made by the IPN as well as by accredited NGOs such as the Polish League Against Defamation. By the same law, the institution's mission statement was changed to include "protecting the reputation of the Republic of Poland and the Polish Nation".

Organisation
IPN was created by special legislation on 18 December 1998. The IPN is divided into:
 * Main Commission for the Prosecution of Crimes against the Polish Nation (Główna Komisja Ścigania Zbrodni Przeciwko Narodowi Polskiemu)
 * Bureau of Provision and Archivization of Documents (Biuro Udostępniania i Archiwizacji Dokumentów)
 * Bureau of Public Education (or Public Education Office, Biuro Edukacji Publicznej)
 * Lustration Bureau (Biuro Lustracyjne) (new bureau, since October 2006)
 * local chapters.

On 29 April 2010, acting president Bronislaw Komorowski signed into law a parliamentary act that reformed the Institute of National Remembrance.

Director
IPN is governed by the director, who has a sovereign position that is independent of the Polish state hierarchy. The director may not be dismissed during his term unless he commits a harmful act. Prior to 2016, the election of the director was a complex procedure, which involves the selection of a panel of candidates by the IPN Collegium (members appointed by the Polish Parliament and judiciary). The Polish Parliament (Sejm) then elects one of the candidates, with a required supermajority (60%). The director has a 5-year term of office. Following 2016 legislation in the PiS controlled parliament, the former pluralist Collegium was replaced with a nine-member Collegium composed of PiS supporters, and the Sejm appoints the director after consulting with the College without an election between candidates.

Leon Kieres
The first director of the IPN was Leon Kieres, elected by the Sejm for five years on 8 June 2000 (term 30 June 2000 – 29 December 2005). The IPN granted some 6,500 people the "victim of communism" status and gathered significant archive material. The IPN faced difficulties since it was new and also since the Democratic Left Alliance (containing former communists) attempted to close the IPN. The publication of Neighbors: The Destruction of the Jewish Community in Jedwabne, Poland by Jan T. Gross, proved to be a lifeline for the IPN as Polish president Aleksander Kwaśniewski intervened to save the IPN since he deemed the IPN's research to be important as part of Jewish-Polish reconciliation and "apology diplomacy".

Janusz Kurtyka
The second director was Janusz Kurtyka, elected on 9 December 2005 with a term that started 29 December 2005 until his death in the Smolensk airplane crash on 10 April 2010. The elections were controversial, as during the elections a leak against Andrzej Przewoźnik accusing him of collaboration with Służba Bezpieczeństwa caused him to withdraw his candidacy. Przewoźnik was cleared of the accusations only after he had lost the election.

In 2006, the IPN opened a "Lustration Bureau" that increased the director's power. The bureau was assigned the task of examining the past of all candidates to public office. Kurtyka widened archive access to the public and shifted focus from compensating victims to researching collaboration.

Franciszek Gryciuk In 1999, historian Franciszek Gryciuk was appointed to the Collegium of the IPN, which he chaired 2003–2004. From June 2008 to June 2011, he was vice president of the IPN. He was acting director 2010–2011, between the death of the IPN's second president, Janusz Kurtyka, in the 2010 Polish Air Force Tu-154 crash and the election of Łukasz Kamiński by the Polish Parliament as the third director.

Łukasz Kamiński
Łukasz Kamiński, was elected by the Sejm in 2011 following the death of his predecessor. Kamiński headed the Wroclaw Regional Bureau of Public Education prior to his election. During his term, the IPN faced a wide array of criticism calling for an overhaul or even replacement. Critics founds fault in the IPN being a state institution, the lack of historical knowledge of its prosecutors, a relatively high number of microhistories with a debatable methodology, overuse of the martyrology motif, research methodology, and isolationism from the wider research community. In response, Kamiński implemented several changes, including organizing public debates with outside historians to counter the charge of isolationism and has suggested refocusing on victims as opposed to agents.

Jarosław Szarek
On 22 July 2016 Jarosław Szarek was appointed to head IPN. He dismissed Krzysztof Persak, co-author of the 2002 two-volume IPN study on the Jedwabne pogrom. In subsequent months, IPN featured in media headlines for releasing controversial documents, including some relating to Lech Wałęsa, for memory politics conducted in schools, for efforts to change Communist street names, and for legislation efforts. According to historian Idesbald Goddeeris, this marks a return of politics to the IPN.

Karol Nawrocki
On 23 July 2021 Karol Nawrocki was appointed to head IPN.

Public prosecutors in the IPN
Two components of the IPN are specialized parts of the Public Prosecution Service of Poland, namely the Main Commission for the Prosecution of Crimes against the Polish Nation and the Lustration Bureau. Each of these two components exercises its activities autonomically from other components of the Institute and is headed by a director who is ex officio Deputy Public Prosecutor General of Poland, while role of the IPN Director is in their case purely accessory and includes no powers regarding conducted investigations, being limited only to providing supporting apparatus and, when vacated, presenting candidates for the offices of the two directors to the Prosecutor General who as their superior has the discretionary power to appoint or reject them.

Main Commission for the Prosecution of Crimes against the Polish Nation
The Main Commission for the Prosecution of Crimes against the Polish Nation (Główna Komisja Ścigania Zbrodni Przeciwko Narodowi Polskiemu) is the oldest component of the IPN tracing its origins to 1945. It investigates and prosecutes crimes committed on Polish soil against Polish citizens as well as people of other citizenships wronged in the country. War crimes which are not affected by statute of limitations according to Polish law include:
 * 1) Crimes of the Soviet and Polish Communist regimes committed in the country from 17 September 1939 until the Fall of Communism on 31 December 1989.
 * 2) Deportations to the Soviet Union of Polish soldiers of Armia Krajowa, and other Polish resistance organizations as well as Polish inhabitants of the former Polish eastern territories.
 * 3) Pacifications of Polish communities between Vistula and Bug rivers in the years 1944 to 1947 by UB-NKVD,
 * 4) Crimes committed by the law enforcement agencies of the Polish People's Republic, particularly Ministry of Public Security of Poland and Main Directorate of Information of the Polish Army.
 * 5) Crimes under the category of war crimes and crimes against humanity.

Lustration Bureau
On 15 March 2007, an amendment to the Polish law regulating the IPN (enacted on 18 December 2006) came into effect. The change gave the IPN new lustration powers and expanded IPN's file access. The change was enacted by Law and Justice government in a series of legislative amendments during 2006 and the beginning of 2007. However, several articles of the 2006-7 amendments were held unconstitutional by Poland's Constitutional Court on 11 May 2007, though the IPN's lustration power was still wider than under the original 1997 law. These powers include loss of position for those who submitted false lustration declarations as well as a lustration process of candidates for senior office.

Research
The research conducted by IPN from December 2000 falls into four main topic areas:
 * Security Apparatus and Civil Resistance (with separate sub-projects devoted to Political Processes and Prisoners 1944–1956, Soviet Repressions and Crimes committed against Polish Citizens and Martial Law: a Glance after Twenty Years);
 * Functioning of the repression apparatus (state security and justice organs) – its organizational structure, cadres and relations with other state authority and party organs
 * Activities of the repression apparatus directed against particular selected social groups and organizations
 * Structure and methods of functioning of the People's Poland security apparatus
 * Security apparatus in combat with the political and military underground 1944–1956
 * Activities of the security apparatus against political emigreés
 * Security apparatus in combat with the Church and freedom of belief
 * Authorities dealing with social crises and democratic opposition in the years 1956–1989 f) List of those repressed and sentenced to death
 * Bibliography of the conspiracy, resistance and repression 1944–1989
 * War, Occupation and the Polish Underground;
 * deepening of knowledge about the structures and activities of the Polish Underground State
 * examination of the human fates in the territories occupied by the Soviet regime and of Poles displaced into the Soviet Union
 * assessment of sources on the living conditions under the Soviet and German Nazi occupations
 * evaluation of the state of research concerning the victims of the war activities and extermination policy of the Soviet and German Nazi occupiers
 * examining the Holocaust (Extermination of Jews) conducted by Nazis in the Polish territories
 * Response of the Polish Underground State to the extermination of Jewish population
 * The Polish Underground press and the Jewish question during the German Nazi occupation
 * Poles and Other Nations in the Years 1939–1989 (with a part on Poles and Ukrainians);
 * Poles and Ukrainians
 * Poles and Lithuanians
 * Poles and Germans
 * Communist authorities – Belarusians – Underground
 * Fate of Jewish people in the People's Republic of Poland
 * Gypsies in Poland
 * Peasants and the People's Authority 1944–1989 (on the situation of peasants and the rural policy in the years 1944–1989)
 * inhabitants of the rural areas during the creation of the totalitarian regime in Poland;
 * peasant life during the Sovietisation of Poland in the years 1948–1956;
 * attitudes of the inhabitants of rural areas towards the state-Church conflict in the years 1956–1970;
 * the role of peasants in the anti-Communist opposition of the 1970s and 1980s.

Education
The IPN's Public Education Office (BEP) vaguely defined role in the IPN act is to inform society of Communist and Nazi crimes and institutions. This vaguely defined role allowed Paweł Machcewicz, BEP's director in 2000, freedom to create a wide range of activities.

Researchers at the IPN conduct not only research but are required to take part in public outreach. BEP has published music CDs, DVDs, and serials. It has founded "historical clubs" for debates and lectures. It has also organized outdoor historical fairs, picnic, and games.

The IPN Bulletin (Biuletyn IPN) is a high circulation popular-scientific journal, intended for lay readers and youth. Some 12,000 of 15,000 copies of the Bulletin are distributed free of charge to secondary schools in Poland, and the rest are sold in bookstores. The Bulletin contains: popular-scientific and academic articles, polemics, manifestos, appeals to readers, promotional material on the IPN and BEP, denials and commentary on reports in the news, as well as multimedia supplements.

The IPN also publishes the Remembrance and Justice (Pamięć i Sprawiedliwość) scientific journal.

The IPN has issued several board games to help educate people about recent Polish history, including:
 * 303 (board game) – a game about the Battle of Britain that focuses on the Polish 303 Squadron.
 * Kolejka – a game about being forced to queue for basic household products during the Communist era.

Naming of monuments
In 2008, the chairman of the IPN wrote to local administrations, calling for the addition of the word "German" before "Nazi" to all monuments and tablets commemorating Germany's victims, stating that "Nazis" is not always understood to relate specifically to Germans. Several scenes of atrocities conducted by Germany were duly updated with commemorative plaques clearly indicating the nationality of the perpetrators. The IPN also requested better documentation and commemoration of crimes that had been perpetrated by the Soviet Union.

The Polish government also asked UNESCO to officially change the name "Auschwitz Concentration Camp" to "Former Nazi German Concentration Camp Auschwitz-Birkenau", to clarify that the camp had been built and operated by Nazi Germany. In 2007, UNESCO's World Heritage Committee changed the camp's name to "Auschwitz Birkenau German Nazi Concentration and Extermination Camp (1940–1945)." Previously some German media, including Der Spiegel, had called the camp "Polish".

Publications
Since 2019, the Institute publishes the Institute of National Remembrance Review, a yearly peer-reviewed academic journal in English, with Anna Karolina Piekarska as editor-in-chief..

Criticism
According to Georges Mink, common criticisms of the IPN include its dominance in the Polish research field, which is guaranteed by a budget that far supersedes that of any similar academic institution; the "thematic monotony ... of micro-historical studies ... of no real scientific interest" of its research; its focus on "martyrology"; and various criticisms of methodology and ethics. Some of these criticisms have been addressed by Director Łukasz Kamiński during his tenure and who according to Mink "has made significant changes"; however, Minsk, writing in 2017, was also concerned with the recent administrative and personnel changes in IPN, including the election of Jarosław Szarek as director, which he posits are likely to result in further the politicization of the IPN. According to Valentin Behr, IPN research into the Communist era is valuable, positing that "the resources at its disposal have made it unrivalled as a research centre in the academic world"; at the same time, he said that the research is mostly focused on the era's negative aspects, and that it "is far from producing a critical approach to history, one that asks its own questions and is methodologically pluralistic." He added that in recent years that problem is being ameliorated as the IPN's work "has somewhat diversified as its administration has taken note of criticism on the part of academics."

According to Robert Traba, "under the ... IPN, tasks related to the 'national politics of memory' were – unfortunately – merged with the mission of independent academic research. In the public mind, there could be only one message flowing from the institute's name: memory and history as a science are one. The problem is that nothing could be further from the truth, and nothing could be more misleading. What the IPN’s message presents, in fact, is the danger that Polish history will be grossly over-simplified." Traba states that "at the heart of debate today is a confrontation between those who support traditional methods and categories of research, and those who support newly defined methods and categories. ... Broadening the research perspective means the enrichment of the historian's instrumentarium.'" He puts the IPN research, in a broad sense, in the former; he states that "[a] solid, workshop-oriented, traditional, and positivist historiography ... which defends itself by the integrity of its analysis and its diversified source base" but criticizes its approach for leading to a "falsely conceived mission to find 'objective truth' at the expense of 'serious study of event history', and a 'simplified claim that only 'secret' sources, not accessible to ordinary mortals', can lead to that objective truth." Traba quotes historian Wiktoria Śliwowska, who wrote: "The historian must strive not only to reconstruct a given reality, but also to understand the background of events, the circumstances in which people acted. It is easy to condemn, but difficult to understand a complicated past. ... [Meanwhile, in the IPN] thick volumes are being produced, into which are being thrown, with no real consideration, further evidence in criminating various persons now deceased (and therefore not able to defend themselves), and elderly people still alive – known and unknown." Traba posits that "there is ... a need for genuine debate that does not revolve around [the files] in the IPN archives, 'lustration,' or short-term and politically inspired discussions designed to establish the 'only real' truth", and suggests that adopting varied perspectives and diverse methodologies might contribute to such debate.

During PiS's control of the government between 2005 and 2007, the IPN was the focus of heated public controversies, in particular in regard to the pasts of Solidarity leader Lech Wałęsa and PZPR secretary Wojciech Jaruzelski. As a result, the IPN has been referred to as "a political institution at the centre of 'memory games'".

In 2008, two IPN employees, Sławomir Cenckiewicz and Piotr Gontarczyk, published a book, SB a Lech Wałęsa (The Security Service and Lech Wałęsa: A Contribution to a Biography) which caused a major controversy. The book's premise was that in the 1970s the Solidarity leader and later president of Poland Lech Wałęsa was a secret informant of the Polish Communist Security Service.

In 2018, the IPN hired Tomasz Greniuch, a historian who in his youth was associated with a far-right group. When he was promoted to a regional director of the Wrocław branch in February 2021, his past came to media attention and resulted in criticism of Greniuch and IPN. Greniuch issued an apology for his past behavior and resigned within weeks.

Organizational and methodological concerns
Valentin Behr writes that the IPN is most "concerned with the production of an official narrative about Poland's recent past" and therefore lacks innovation in its research, while noting that situation is being remedied under recent leadership. He writes that the IPN "has mainly taken in historians from the fringes of the academic field" who were either unable to obtain a prominent academic position or ideologically drawn to the IPN's approach, and that "in the academic field, being an 'IPN historian' can be a stigma"; Behr explains this by pointing to a generational divide in Polish academia, visible when comparing IPN to other Polish research outlets, and claims: "Hiring young historians was done deliberately to give the IPN greater autonomy from the academic world, considered as too leftist to describe the dark sides of the communist regime." He says that the IPN has created opportunities for many history specialists who can carry dedicated research there without the need for an appointment at another institution, and for training young historians, noting that "the IPN is now the leading employer of young PhD students and PhDs in history specialized in contemporary history, ahead of Polish universities".

Historian Dariusz Stola states that the IPN is very bureaucratic in nature, comparing it to a "regular continental European bureaucracy, with usual deficiencies of its kind", and posits that in this aspect the IPN resembles the former Communist institutions it is supposed to deal with, equally "bureaucratic, centralist, heavy, inclined to extensive growth and quantity rather than quality of production".

An incident which caused controversy involved the "Wildstein list", a partial list of persons who allegedly worked for the communist-era Polish intelligence service, copied in 2004 from IPN archives (without IPN permission) by journalist Bronisław Wildstein and published on the Internet in 2005. The list gained much attention in Polish media and politics, and IPN security procedures and handling of the matter came under criticism.

title: Institute of National Remembrance


text:
Intelligence (disambiguation)

Intelligence is the ability to perceive, collect, or infer information, retain it, and make decisions based on that information.

Intelligence or intelligent may refer to:

Disciplines

 * Intelligence analysis
 * Espionage, intelligence gathering
 * Business intelligence, for business analysis purposes
 * Military intelligence, a military discipline using information collection and analysis
 * Strategic intelligence, information collection and analysis the national and international level to include non-military organizations
 * Signals intelligence

Organizations

 * Intelligence agency
 * Police intelligence, an element of the British police

Human capacities

 * Human intelligence
 * Emotional intelligence
 * Social intelligence

Music

 * "Intelligence", a song by ...And You Will Know Us by the Trail of Dead from the 2003 EP The Secret of Elena's Tomb
 * The Intelligence, an American rock band
 * Intelligence, an opera with libretto by Gene Scheer
 * Intelligent dance music

Literature

 * Intelligence (journal), a scientific journal dealing with intelligence and psychometrics
 * Intelligence (newspaper), an Australian newspaper

Television

 * Intelligence (Canadian TV series), 2006–2007
 * Intelligence (American TV series), 2014
 * Intelligence (British TV series), 2020
 * Inttelligent, a 2018 Indian Telugu-language film

Games

 * Intelligence (solitaire), a card game

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Intelligence (disambiguation)


text:
Indistinguishable particles

In quantum mechanics, indistinguishable particles (also called identical or indiscernible particles) are particles that cannot be distinguished from one another, even in principle. Species of identical particles include, but are not limited to, elementary particles (such as electrons), composite subatomic particles (such as atomic nuclei), as well as atoms and molecules. Quasiparticles also behave in this way. Although all known indistinguishable particles only exist at the quantum scale, there is no exhaustive list of all possible sorts of particles nor a clear-cut limit of applicability, as explored in quantum statistics. They were first discussed by Werner Heisenberg and Paul Dirac in 1926.

There are two main categories of identical particles: bosons, which can share quantum states, and fermions, which cannot (as described by the Pauli exclusion principle). Examples of bosons are photons, gluons, phonons, helium-4 nuclei and all mesons. Examples of fermions are electrons, neutrinos, quarks, protons, neutrons, and helium-3 nuclei.

The fact that particles can be identical has important consequences in statistical mechanics, where calculations rely on probabilistic arguments, which are sensitive to whether or not the objects being studied are identical. As a result, identical particles exhibit markedly different statistical behaviour from distinguishable particles. For example, the indistinguishability of particles has been proposed as a solution to Gibbs' mixing paradox.

Distinguishing between particles
There are two methods for distinguishing between particles. The first method relies on differences in the intrinsic physical properties of the particles, such as mass, electric charge, and spin. If differences exist, it is possible to distinguish between the particles by measuring the relevant properties. However, as far as can be determined, microscopic particles of the same species have completely equivalent physical properties. For instance, every electron has the same electric charge.

Even if the particles have equivalent physical properties, there remains a second method for distinguishing between particles, which is to track the trajectory of each particle. As long as the position of each particle can be measured with infinite precision (even when the particles collide), then there would be no ambiguity about which particle is which.

The problem with the second approach is that it contradicts the principles of quantum mechanics. According to quantum theory, the particles do not possess definite positions during the periods between measurements. Instead, they are governed by wavefunctions that give the probability of finding a particle at each position. As time passes, the wavefunctions tend to spread out and overlap. Once this happens, it becomes impossible to determine, in a subsequent measurement, which of the particle positions correspond to those measured earlier. The particles are then said to be indistinguishable.

Symmetrical and antisymmetrical states

What follows is an example to make the above discussion concrete, using the formalism developed in the article on the mathematical formulation of quantum mechanics.

Let n denote a complete set of (discrete) quantum numbers for specifying single-particle states (for example, for the particle in a box problem, take n to be the quantized wave vector of the wavefunction.) For simplicity, consider a system composed of two particles that are not interacting with each other. Suppose that one particle is in the state n1, and the other is in the state n2. The quantum state of the system is denoted by the expression
 * $$ | n_1 \rang | n_2 \rang $$

where the order of the tensor product matters ( if $$ | n_2 \rang | n_1 \rang $$, then the particle 1 occupies the state n2 while the particle 2 occupies the state n1). This is the canonical way of constructing a basis for a tensor product space $$H \otimes H$$ of the combined system from the individual spaces. This expression is valid for distinguishable particles, however, it is not appropriate for indistinguishable particles since $$ |n_1\rang |n_2\rang$$ and $$|n_2\rang |n_1\rang $$ as a result of exchanging the particles are generally different states.
 * "the particle 1 occupies the n1 state and the particle 2 occupies the n2 state" ≠ "the particle 1 occupies the n2 state and the particle 2 occupies the n1 state".

Two states are physically equivalent only if they differ at most by a complex phase factor. For two indistinguishable particles, a state before the particle exchange must be physically equivalent to the state after the exchange, so these two states differ at most by a complex phase factor. This fact suggests that a state for two indistinguishable (and non-interacting) particles is given by following two possibilities:
 * $$ |n_1\rang |n_2\rang \pm |n_2\rang |n_1\rang $$

States where it is a sum are known as symmetric, while states involving the difference are called antisymmetric. More completely, symmetric states have the form
 * $$ |n_1, n_2; S\rang \equiv \mbox{constant} \times \bigg( |n_1\rang |n_2\rang + |n_2\rang |n_1\rang \bigg) $$

while antisymmetric states have the form
 * $$ |n_1, n_2; A\rang \equiv \mbox{constant} \times \bigg( |n_1\rang |n_2\rang - |n_2\rang |n_1\rang \bigg) $$

Note that if n1 and n2 are the same, the antisymmetric expression gives zero, which cannot be a state vector since it cannot be normalized. In other words, more than one identical particle cannot occupy an antisymmetric state (one antisymmetric state can be occupied only by one particle). This is known as the Pauli exclusion principle, and it is the fundamental reason behind the chemical properties of atoms and the stability of matter.

Exchange symmetry
The importance of symmetric and antisymmetric states is ultimately based on empirical evidence. It appears to be a fact of nature that identical particles do not occupy states of a mixed symmetry, such as
 * $$ |n_1, n_2; ?\rang = \mbox{constant} \times \bigg( |n_1\rang |n_2\rang + i |n_2\rang |n_1\rang \bigg) $$

There is actually an exception to this rule, which will be discussed later. On the other hand, it can be shown that the symmetric and antisymmetric states are in a sense special, by examining a particular symmetry of the multiple-particle states known as exchange symmetry.

Define a linear operator P, called the exchange operator. When it acts on a tensor product of two state vectors, it exchanges the values of the state vectors:
 * $$P \bigg(|\psi\rang |\phi\rang \bigg) \equiv |\phi\rang |\psi\rang $$

P is both Hermitian and unitary. Because it is unitary, it can be regarded as a symmetry operator. This symmetry may be described as the symmetry under the exchange of labels attached to the particles (i.e., to the single-particle Hilbert spaces).

Clearly, $$P^2 = 1$$ (the identity operator), so the eigenvalues of P are +1 and −1. The corresponding eigenvectors are the symmetric and antisymmetric states:
 * $$P|n_1, n_2; S\rang = + |n_1, n_2; S\rang$$
 * $$P|n_1, n_2; A\rang = - |n_1, n_2; A\rang$$

In other words, symmetric and antisymmetric states are essentially unchanged under the exchange of particle labels: they are only multiplied by a factor of +1 or −1, rather than being "rotated" somewhere else in the Hilbert space. This indicates that the particle labels have no physical meaning, in agreement with the earlier discussion on indistinguishability.

It will be recalled that P is Hermitian. As a result, it can be regarded as an observable of the system, which means that, in principle, a measurement can be performed to find out if a state is symmetric or antisymmetric. Furthermore, the equivalence of the particles indicates that the Hamiltonian can be written in a symmetrical form, such as
 * $$H = \frac{p_1^2}{2m} + \frac{p_2^2}{2m} + U(|x_1 - x_2|) + V(x_1) + V(x_2) $$

It is possible to show that such Hamiltonians satisfy the commutation relation
 * $$\left[P, H\right] = 0$$

According to the Heisenberg equation, this means that the value of P is a constant of motion. If the quantum state is initially symmetric (antisymmetric), it will remain symmetric (antisymmetric) as the system evolves. Mathematically, this says that the state vector is confined to one of the two eigenspaces of P, and is not allowed to range over the entire Hilbert space. Thus, that eigenspace might as well be treated as the actual Hilbert space of the system. This is the idea behind the definition of Fock space.

Fermions and bosons
The choice of symmetry or antisymmetry is determined by the species of particle. For example, symmetric states must always be used when describing photons or helium-4 atoms, and antisymmetric states when describing electrons or protons.

Particles which exhibit symmetric states are called bosons. The nature of symmetric states has important consequences for the statistical properties of systems composed of many identical bosons. These statistical properties are described as Bose–Einstein statistics.

Particles which exhibit antisymmetric states are called fermions. Antisymmetry gives rise to the Pauli exclusion principle, which forbids identical fermions from sharing the same quantum state. Systems of many identical fermions are described by Fermi–Dirac statistics.

Parastatistics are mathematically possible, but no examples exist in nature.

In certain two-dimensional systems, mixed symmetry can occur. These exotic particles are known as anyons, and they obey fractional statistics. Experimental evidence for the existence of anyons exists in the fractional quantum Hall effect, a phenomenon observed in the two-dimensional electron gases that form the inversion layer of MOSFETs. There is another type of statistic, known as braid statistics, which are associated with particles known as plektons.

The spin-statistics theorem relates the exchange symmetry of identical particles to their spin. It states that bosons have integer spin, and fermions have half-integer spin. Anyons possess fractional spin.

N particles
The above discussion generalizes readily to the case of N particles. Suppose there are N particles with quantum numbers n1, n2, ..., nN. If the particles are bosons, they occupy a totally symmetric state, which is symmetric under the exchange of any two particle labels:
 * $$|n_1 n_2 \cdots n_N; S\rang = \sqrt{\frac{\prod_n m_n!}{N!}} \sum_p \left|n_{p(1)}\right\rang \left|n_{p(2)}\right\rang \cdots \left|n_{p(N)}\right\rang $$

Here, the sum is taken over all different states under permutations p acting on N elements. The square root left to the sum is a normalizing constant. The quantity mn stands for the number of times each of the single-particle states n appears in the N-particle state. Note that Σn mn = N.

In the same vein, fermions occupy totally antisymmetric states:
 * $$|n_1 n_2 \cdots n_N; A\rang = \frac{1}{\sqrt{N!}} \sum_p \operatorname{sgn}(p) \left|n_{p(1)}\right\rang \left|n_{p(2)}\right\rang \cdots \left|n_{p(N)}\right\rang\ $$

Here, $sgn(p)$ is the sign of each permutation (i.e. $$+1$$ if $$p$$ is composed of an even number of transpositions, and $$-1$$ if odd). Note that there is no $$\Pi_n m_n$$ term, because each single-particle state can appear only once in a fermionic state. Otherwise the sum would again be zero due to the antisymmetry, thus representing a physically impossible state. This is the Pauli exclusion principle for many particles.

These states have been normalized so that
 * $$ \lang n_1 n_2 \cdots n_N; S | n_1 n_2 \cdots n_N; S\rang = 1, \qquad \lang n_1 n_2 \cdots n_N; A | n_1 n_2 \cdots n_N; A\rang = 1. $$

Measurement
Suppose there is a system of N bosons (fermions) in the symmetric (antisymmetric) state
 * $$|n_1 n_2 \cdots n_N; S/A \rang$$

and a measurement is performed on some other set of discrete observables, m. In general, this yields some result m1 for one particle, m2 for another particle, and so forth. If the particles are bosons (fermions), the state after the measurement must remain symmetric (antisymmetric), i.e.
 * $$|m_1 m_2 \cdots m_N; S/A \rang$$

The probability of obtaining a particular result for the m measurement is
 * $$P_{S/A}\left(n_1, \ldots, n_N \rightarrow m_1, \ldots, m_N\right) \equiv \big|\left\lang m_1 \cdots m_N; S/A \,|\, n_1 \cdots n_N; S/A \right\rang \big|^2 $$

It can be shown that
 * $$\sum_{m_1 \le m_2 \le \dots \le m_N} P_{S/A}(n_1, \ldots, n_N \rightarrow m_1, \ldots, m_N) = 1$$

which verifies that the total probability is 1. The sum has to be restricted to ordered values of m1, ..., mN to ensure that each multi-particle state is not counted more than once.

Wavefunction representation
So far, the discussion has included only discrete observables. It can be extended to continuous observables, such as the position x.

Recall that an eigenstate of a continuous observable represents an infinitesimal range of values of the observable, not a single value as with discrete observables. For instance, if a particle is in a state |ψ⟩, the probability of finding it in a region of volume d3x surrounding some position x is
 * $$ |\lang x | \psi \rang|^2 \; d^3 x $$

As a result, the continuous eigenstates |x⟩ are normalized to the delta function instead of unity:
 * $$ \lang x | x' \rang = \delta^3 (x - x') $$

Symmetric and antisymmetric multi-particle states can be constructed from continuous eigenstates in the same way as before. However, it is customary to use a different normalizing constant:
 * $$\begin{align}

|x_1 x_2 \cdots x_N; S\rang &= \sqrt{\frac{\prod_j n_j!}{N!}} \sum_p \left|x_{p(1)}\right\rang \left|x_{p(2)}\right\rang \cdots \left|x_{p(N)}\right\rang \\ |x_1 x_2 \cdots x_N; A\rang &= \frac{1}{\sqrt{N!}} \sum_p \mathrm{sgn}(p) \left|x_{p(1)}\right\rang \left|x_{p(2)}\right\rang \cdots \left|x_{p(N)}\right\rang \end{align}$$

A many-body wavefunction can be written,
 * $$\begin{align}

\Psi^{(S)}_{n_1 n_2 \cdots n_N} (x_1, x_2, \ldots, x_N) & \equiv \lang x_1 x_2 \cdots x_N; S | n_1 n_2 \cdots n_N; S \rang \\[4pt] & = \sqrt{\frac{\prod_j n_j!}{N!}} \sum_p \psi_{p(1)}(x_1) \psi_{p(2)}(x_2) \cdots \psi_{p(N)}(x_N) \\[10pt] \Psi^{(A)}_{n_1 n_2 \cdots n_N} (x_1, x_2, \ldots, x_N) & \equiv \lang x_1 x_2 \cdots x_N; A | n_1 n_2 \cdots n_N; A \rang \\[4pt] & = \frac{1}{\sqrt{N!}} \sum_p \mathrm{sgn}(p) \psi_{p(1)}(x_1) \psi_{p(2)}(x_2) \cdots \psi_{p(N)}(x_N) \end{align}$$ where the single-particle wavefunctions are defined, as usual, by
 * $$\psi_n(x) \equiv \lang x | n \rang $$

The most important property of these wavefunctions is that exchanging any two of the coordinate variables changes the wavefunction by only a plus or minus sign. This is the manifestation of symmetry and antisymmetry in the wavefunction representation:
 * $$\begin{align}

\Psi^{(S)}_{n_1 \cdots n_N} (\cdots x_i \cdots x_j\cdots) = \Psi^{(S)}_{n_1 \cdots n_N} (\cdots x_j \cdots x_i \cdots) \\[3pt] \Psi^{(A)}_{n_1 \cdots n_N} (\cdots x_i \cdots x_j\cdots) = -\Psi^{(A)}_{n_1 \cdots n_N} (\cdots x_j \cdots x_i \cdots) \end{align}$$

The many-body wavefunction has the following significance: if the system is initially in a state with quantum numbers n1, ..., nN, and a position measurement is performed, the probability of finding particles in infinitesimal volumes near x1, x2, ..., xN is
 * $$ N! \; \left|\Psi^{(S/A)}_{n_1 n_2 \cdots n_N} (x_1, x_2, \ldots, x_N) \right|^2 \; d^{3N}\!x $$

The factor of N! comes from our normalizing constant, which has been chosen so that, by analogy with single-particle wavefunctions,
 * $$ \int\!\int\!\cdots\!\int\; \left|\Psi^{(S/A)}_{n_1 n_2 \cdots n_N} (x_1, x_2, \ldots, x_N)\right|^2 d^3\!x_1 d^3\!x_2 \cdots d^3\!x_N = 1 $$

Because each integral runs over all possible values of x, each multi-particle state appears N! times in the integral. In other words, the probability associated with each event is evenly distributed across N! equivalent points in the integral space. Because it is usually more convenient to work with unrestricted integrals than restricted ones, the normalizing constant has been chosen to reflect this.

Finally, antisymmetric wavefunction can be written as the determinant of a matrix, known as a Slater determinant:
 * $$\Psi^{(A)}_{n_1 \cdots n_N} (x_1, \ldots, x_N) =

\frac{1}{\sqrt{N!}} \left| \begin{matrix} \psi_{n_1}(x_1) & \psi_{n_1}(x_2) & \cdots & \psi_{n_1}(x_N) \\ \psi_{n_2}(x_1) & \psi_{n_2}(x_2) & \cdots & \psi_{n_2}(x_N) \\ \vdots &         \vdots & \ddots &          \vdots \\ \psi_{n_N}(x_1) & \psi_{n_N}(x_2) & \cdots & \psi_{n_N}(x_N) \\ \end{matrix} \right| $$

Operator approach and parastatistics
The Hilbert space for $$n$$ particles is given by the tensor product $ \bigotimes_n H $. The permutation group of $$ S_n $$ acts on this space by permuting the entries. By definition the expectation values for an observable $$a$$ of $$n$$ indistinguishable particles should be invariant under these permutation. This means that for all $$ \psi \in H $$ and $$ \sigma \in S_n $$
 * $$ (\sigma \Psi )^t a (\sigma \Psi)   = \Psi^t a \Psi,$$

or equivalently for each $$ \sigma \in S_n $$
 * $$ \sigma^t a \sigma = a $$.

Two states are equivalent whenever their expectation values coincide for all observables. If we restrict to observables of $$n $$ identical particles, and hence observables satisfying the equation above, we find that the following states (after normalization) are equivalent
 * $$ \Psi \sim \sum_{\sigma \in S_n} \lambda_{\sigma} \sigma \Psi$$.

The equivalence classes are in bijective relation with irreducible subspaces of $ \bigotimes_n H $ under $$ S_n $$.

Two obvious irreducible subspaces are the one dimensional symmetric/bosonic subspace and anti-symmetric/fermionic subspace. There are however more types of irreducible subspaces. States associated with these other irreducible subspaces are called parastatistic states. Young tableaux provide a way to classify all of these irreducible subspaces.

Statistical effects of indistinguishability
The indistinguishability of particles has a profound effect on their statistical properties. To illustrate this, consider a system of N distinguishable, non-interacting particles. Once again, let nj denote the state (i.e. quantum numbers) of particle j. If the particles have the same physical properties, the njs run over the same range of values. Let ε(n) denote the energy of a particle in state n. As the particles do not interact, the total energy of the system is the sum of the single-particle energies. The partition function of the system is
 * $$ Z = \sum_{n_1, n_2, \ldots, n_N} \exp\left\{ -\frac{1}{kT} \left[ \varepsilon(n_1) + \varepsilon(n_2) + \cdots + \varepsilon(n_N) \right] \right\} $$

where k is the Boltzmann constant and T is the temperature. This expression can be factored to obtain
 * $$ Z = \xi^N $$

where
 * $$ \xi = \sum_n \exp\left[ - \frac{\varepsilon(n)}{kT} \right].$$

If the particles are identical, this equation is incorrect. Consider a state of the system, described by the single particle states [n1, ..., nN]. In the equation for Z, every possible permutation of the ns occurs once in the sum, even though each of these permutations is describing the same multi-particle state. Thus, the number of states has been over-counted.

If the possibility of overlapping states is neglected, which is valid if the temperature is high, then the number of times each state is counted is approximately N ! . The correct partition function is
 * $$ Z = \frac{\xi^N}{N!}.$$

Note that this "high temperature" approximation does not distinguish between fermions and bosons.

The discrepancy in the partition functions of distinguishable and indistinguishable particles was known as far back as the 19th century, before the advent of quantum mechanics. It leads to a difficulty known as the Gibbs paradox. Gibbs showed that in the equation Z = ξN, the entropy of a classical ideal gas is
 * $$S = N k \ln \left(V\right) + N f(T)$$

where V is the volume of the gas and f is some function of T alone. The problem with this result is that S is not extensive – if N and V are doubled, S does not double accordingly. Such a system does not obey the postulates of thermodynamics.

Gibbs also showed that using Z = ξN/N! alters the result to
 * $$S = N k \ln \left(\frac{V}{N}\right) + N f(T)$$

which is perfectly extensive. However, the reason for this correction to the partition function remained obscure until the discovery of quantum mechanics

Statistical properties of bosons and fermions
There are important differences between the statistical behavior of bosons and fermions, which are described by Bose–Einstein statistics and Fermi–Dirac statistics respectively. Roughly speaking, bosons have a tendency to clump into the same quantum state, which underlies phenomena such as the laser, Bose–Einstein condensation, and superfluidity. Fermions, on the other hand, are forbidden from sharing quantum states, giving rise to systems such as the Fermi gas. This is known as the Pauli Exclusion Principle, and is responsible for much of chemistry, since the electrons in an atom (fermions) successively fill the many states within shells rather than all lying in the same lowest energy state.

The differences between the statistical behavior of fermions, bosons, and distinguishable particles can be illustrated using a system of two particles. The particles are designated A and B. Each particle can exist in two possible states, labelled $$|0\rangle$$ and $$|1\rangle$$, which have the same energy.

The composite system can evolve in time, interacting with a noisy environment. Because the $$|0\rangle$$ and $$|1\rangle$$ states are energetically equivalent, neither state is favored, so this process has the effect of randomizing the states. (This is discussed in the article on quantum entanglement.) After some time, the composite system will have an equal probability of occupying each of the states available to it. The particle states are then measured.

If A and B are distinguishable particles, then the composite system has four distinct states: $$|0\rangle|0\rangle$$, $$|1\rangle|1\rangle$$, $$|0\rangle|1\rangle$$, and $$|1\rangle|0\rangle$$. The probability of obtaining two particles in the $$|0\rangle$$ state is 0.25; the probability of obtaining two particles in the $$|1\rangle$$ state is 0.25; and the probability of obtaining one particle in the $$|0\rangle$$ state and the other in the $$|1\rangle$$ state is 0.5.

If A and B are identical bosons, then the composite system has only three distinct states: $$|0\rangle|0\rangle$$, $$|1\rangle|1\rangle$$, and $$\frac{1}{\sqrt{2}}(|0\rangle|1\rangle + |1\rangle|0\rangle)$$. When the experiment is performed, the probability of obtaining two particles in the $$|0\rangle$$ state is now 0.33; the probability of obtaining two particles in the $$|1\rangle$$ state is 0.33; and the probability of obtaining one particle in the $$|0\rangle$$ state and the other in the $$|1\rangle$$ state is 0.33. Note that the probability of finding particles in the same state is relatively larger than in the distinguishable case. This demonstrates the tendency of bosons to "clump".

If A and B are identical fermions, there is only one state available to the composite system: the totally antisymmetric state $$\frac{1}{\sqrt{2}}(|0\rangle|1\rangle - |1\rangle|0\rangle)$$. When the experiment is performed, one particle is always in the $$|0\rangle$$ state and the other is in the $$|1\rangle$$ state.

The results are summarized in Table 1:

As can be seen, even a system of two particles exhibits different statistical behaviors between distinguishable particles, bosons, and fermions. In the articles on Fermi–Dirac statistics and Bose–Einstein statistics, these principles are extended to large number of particles, with qualitatively similar results.

Homotopy class
To understand why particle statistics work the way that they do, note first that particles are point-localized excitations and that particles that are spacelike separated do not interact. In a flat $d$-dimensional space $M$, at any given time, the configuration of two identical particles can be specified as an element of $M × M$. If there is no overlap between the particles, so that they do not interact directly, then their locations must belong to the space $[M × M] \ {coincident points},$ the subspace with coincident points removed. The element $(x, y)$ describes the configuration with particle I at $x$ and particle II at $y$, while $(y, x)$ describes the interchanged configuration. With identical particles, the state described by $(x, y)$ ought to be indistinguishable from the state described by $(y, x)$. Now consider the homotopy class of continuous paths from $(x, y)$ to $(y, x)$, within the space $[M × M] \ {coincident points}$. If $M$ is $\mathbb R^d$ where $d ≥ 3$, then this homotopy class only has one element. If $M$ is $\mathbb R^2$, then this homotopy class has countably many elements (i.e. a counterclockwise interchange by half a turn, a counterclockwise interchange by one and a half turns, two and a half turns, etc., a clockwise interchange by half a turn, etc.). In particular, a counterclockwise interchange by half a turn is not homotopic to a clockwise interchange by half a turn. Lastly, if $M$ is $\mathbb R$, then this homotopy class is empty.

Suppose first that $d ≥ 3$. The universal covering space of $[M × M] ∖ \{coincident points\}$, which is none other than $[M × M] ∖ \{coincident points\}$ itself, only has two points which are physically indistinguishable from $(x, y)$, namely $(x, y)$ itself and $(y, x)$. So, the only permissible interchange is to swap both particles. This interchange is an involution, so its only effect is to multiply the phase by a square root of 1. If the root is +1, then the points have Bose statistics, and if the root is –1, the points have Fermi statistics.

In the case $$M = \mathbb R^2,$$ the universal covering space of $[M × M] ∖ \{coincident points\}$ has infinitely many points that are physically indistinguishable from $(x, y)$. This is described by the infinite cyclic group generated by making a counterclockwise half-turn interchange. Unlike the previous case, performing this interchange twice in a row does not recover the original state; so such an interchange can generically result in a multiplication by $exp(iθ)$ for any real $θ$ (by unitarity, the absolute value of the multiplication must be 1). This is called anyonic statistics. In fact, even with two distinguishable particles, even though $(x, y)$ is now physically distinguishable from $(y, x)$, the universal covering space still contains infinitely many points which are physically indistinguishable from the original point, now generated by a counterclockwise rotation by one full turn. This generator, then, results in a multiplication by $exp(iφ)$. This phase factor here is called the mutual statistics.

Finally, in the case $$M = \mathbb R,$$ the space $[M × M] ∖ \{coincident points\}$ is not connected, so even if particle I and particle II are identical, they can still be distinguished via labels such as "the particle on the left" and "the particle on the right". There is no interchange symmetry here.

title: Indistinguishable particles


text:
Talk:Insertion sort

human sorting
the article says Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.[1]

I beg to differ. Almost all people I know when sorting a deck of cards use something like intro sort. That is, they divide the deck into four decks, like a step of quick sort would do, and then they either sort insertion sort like the single decks, or some people sort the single decks into "Numbers" and "pictures" and then sort them as insertion sort. that is more like intro sort.

Also when people sort lego bricks, I saw mostly things like sorting colors first, then all one-row and all two-row on a pile, then divide them into long and short piles and so on. When doing a jigsaw puzzle, I saw a lot of people to make little piles that seem to belong together. This all resembles more algorithms like quicksort, introsort and radixsort... —Preceding unsigned comment added by 213.61.9.75 (talk) 14:22, 13 May 2011 (UTC)

Standardization
Shouldn't this article be more structurally similar to the Merge Sort article? --Guugolpl0x (talk) 03:58, 6 September 2010 (UTC)

improvement
This sample code is simple but is not efficient.

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.

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 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:

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:

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

 * 1) include
 * 2) include
 * 3) include

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
As you will learn in very Computer Science class pseudocode is not intended to be implementable. Also expressions like "count++" or operators like "&&" are frowned upon because the may be ambigous between languages. — Preceding unsigned comment added by 78.55.242.110 (talk) 16:14, 5 February 2014 (UTC)

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)

Pseudocode error
The pseudocode example contains an indexing error!!

I'm pretty sure you cannot have a zero-based index run from 1 to N, and then attempt to get a value for a[i] - this element cannot EXIST! 12.27.253.143 (talk) 21:09, 29 July 2014 (UTC)

This is true. I have change the pseudocode so that i ranges from 1 to length(A)-1. 124.148.192.50 (talk) 03:06, 21 May 2016 (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)

Replaced average running time claims with big O complexity
In the listing of the advantages of insertion sort, it says that the average running time is n2/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)

 * Absolutely. I've replaced this:
 * with this:
 * I've also changed the title of this talk section from "What does running time in this context mean?" to "Replaced average running time claims with big O complexity" Alex.mccarthy (talk) 18:22, 21 May 2010 (UTC)
 * I've also changed the title of this talk section from "What does running time in this context mean?" to "Replaced average running time claims with big O complexity" Alex.mccarthy (talk) 18:22, 21 May 2010 (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)

Yes I agree that the extra begin/do is redundant, but I didn't want to change things too much as there seems to be some kind of pascal v python religious war in the history of this page that I wanted to avoid. I think the most important thing is to go with one of these suggestions and get the algorithm clear as at the moment it is not a positive addition to the page. 82.24.215.72 (talk) 19:37, 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)

It would be prudent for you to read the articles on some of the other algorithms and have a look at http://www.sorting-algorithms.com to see what animations of sorting looks like before you comment. As for proofs, if you are at all familiar with computer science or mathematics you should know animations are not an acceptable method of proof, the point of the animation is to provide a depiction of how the algorithm works. The animation is useful as a demonstration as many people are visual thinkers and it helps them to understand what is happening during an insertion sort. Certainly, the animation could be improved, but it is not useless.

I suggest you finish the sophomore year of a computer science or math degree before you comment on how you think elements of a very well thought-out Wikipedia are useless. Asdquefty (talk) 19:41, 4 May 2010 (UTC)

First of all, I really didn't appreciate you offending me like that. I suggestion was in good faith, and obviously you did not take it as such. That animation on the site you linked to (which I have seen before too) does accurately show what the algorithm is doing in each case, and in my opinion is tremendously better than the animation on this page. Even something like the selection sort animation here: http://en.wikipedia.org/wiki/File:Selection-Sort-Animation.gif would be better suited. 76.67.115.46 (talk) 15:04, 9 May 2010 (UTC)

I agree that the animation is indeed useless. The animation should show each comparison required for the element being inserted for it to be useful. e.g. the inserted value would slowly move from the right to the left, one element at a time until it reaches its place in the array, because this accurately reflects the actual processing time of the algorithm. As it is now, it looks like the element immediately jumps to the correct place in the array, and any input would run in O(n) time, which is obviously wrong. Two images, one showing a relatively sorted initial array, and one showing an input with reverse initial sorting would demonstrate the huge difference in runtime for these min and max inputs. 66.72.215.225 (talk) 18:55, 3 September 2010 (UTC)

List insertion sort code in C++ section
I replaced the Insertion sort section. It had a lot of syntax, little content, took n as an argument, the v were in an array rather than a list, and it created an aux link array for the sort. It was not a list sort.

A list insertion sort pops items off the input list and then splices them into a built up sorted list. When the input list is empty, the algorithm is done (with a possible NREVERSE).

I used a trailing pointer algorithm -- more efficient but less clear.

Glrx (talk) 22:17, 13 December 2011 (UTC)

A little bit beyond this algo
im not sucha great encoder, i just think there could b useful to use some O(k) mem to form a sorted buffer n help insert it

multidimensional ques might b some hybrid from arraies n sorting trees, i guess, the main goal would b using less mem to "control" their access

again, im a poor encoder, my strong point is solving relatevely heavy math problems these ones, sorting i mean, looks a bit noncreatively approached, after my judgement, i mean ok enough with Romanian boring time 4 now :-)

93.118.212.93 (talk) 18:36, 8 February 2013 (UTC)

basically insertion sort, but fast
1 million sorted in 1 second... compiled with qb64 enviroment

'wow !!! superinsertion ;))

— Preceding unsigned comment added by 93.118.212.93 (talk) 15:25, 17 February 2013 (UTC)

 * I'm not sure what that is, but it's not an "insertion" sort. — Arthur Rubin  (talk) 16:01, 17 February 2013 (UTC)

again, abt algos that r inspired from insertion sort :)
this (new) idea works recursevely and, in order to offer room for a linear multiinsertion (at least in some hypotetical terms), sorts b4 the lower half of the curently remaining amount to b inserted, idea being that we got (all the) conditions to inset this half of remaining amount to b inseted, sorted also in O(N). im sorry to tell u that but idk if its really working, nor that abt its O n neither if its also discovered, in case its working. im just following some of my own preocupation in searching for appealing paradigms :) Florin Matei, Romania 93.118.212.93 (talk) 12:37, 15 April 2013 (UTC)

Pseudocode Results in Descending Order
While the pseudocode indeed sorts the array, it does so in descending order. This does not seem like the expected result, since all of the surrounding examples --- the diagrams and the animation --- demonstrate ascending sorts.

To rectify, the third line should employ less-than for the array element comparison:.

Also, while minor, I think the fourth line would read better with the array elements flipped:. It has better visual symmetry with the preceding line.

Njuk-njuk (talk) 02:35, 7 August 2015 (UTC)

I was wondering if anyone knew a bit of history behind the Insertion Sort algorithm. Hence, where it came from, when it was first published, etc. If anyone has some good resources I would be very glad and thankful if they shared them. Thanks! — Preceding unsigned comment added by Chromechris (talk • contribs) 18:35, 16 March 2017 (UTC)

pseudo code for loop
The for loops in the first two pseudo code examples don't make it clear what the terminating value is: with for i = 1 to length(A), it isn't clear if the last value for i is length(A)-1 or length(A). I'm not aware of a programming language that uses the examples version of for loops. Fortran: do i = 0, n is inclusive, the last value for i is n. C, C++, Java, make it clear using a specific terminator condition: for(i = 1; i < n; i = i + 1), the last value for i is n-1. Python relies on functions in it's for statements like for i in range(0,n), where range is not part of the for loop but a function that generates a list (array) of numbers 0 to n-1, or for i in xrange(0,n), where xrange generates the indices 0 to n-1 one at a time. I suggest using C / C++ / Java style syntax, or separating the for loop into 4 statements: i ← 1, while(i < length(A)), ..., i ← i + 1, end while. Rcgldr (talk) 19:32, 15 July 2017 (UTC)

Pseudocode for a quicksort optimization using insertion sort
I have removed the quicksort pseudocode in the section "Relation to other sorting algorithms." Not only do I believe that is better placed in the main article, but that particular variant of the optimization isn't widely used anymore anyway (as described in the main article, section 2.3.3 "Optimizations", third bullet point). Derek M (talk) 01:44, 17 January 2018 (UTC)

C three-line implementation not verifiable?
The article uses an example of a 3 LOC C implementation to demonstrate the algorithms simplicity. I have obtained a digital copy of a book with a matching name and author, but the contents seem to differ and the description and cover seem to refer to a completely different book. In any case, it seems appropriate to remove. 109.43.113.6 (talk) 18:42, 24 December 2021 (UTC)

 * Google books shows that page 116 of the cited book has a three-line insertion sort. You may not have the same edition of the book. StarryGrandma (talk) 20:13, 26 December 2021 (UTC)

Insertion sort
Nothing 2409:4073:5:4DDA:576D:5CCC:FB34:20FD (talk) 07:01, 1 July 2022 (UTC)
 * Can you elaborate a bit? --CiaPan (talk) 10:31, 1 July 2022 (UTC)

"←" Symbol in Pseudocode Examples
Using "←" as a replacement for "=" is harder to understand, and I don't see a reason for it. Noice65535 (talk) 21:56, 29 July 2023 (UTC)

While Loop?
Is there any reason that a while loop is used instead of a for loop? For example, if one were to implement it, it'd most likely look something like

void sort (float A[], int n) { float temp; for (unsigned int i = 1; i < n; i++) { for (unsigned int j = i; j > 0 && A[j] < a[j - 1];) { temp = a[j]; a[j] = a[--j]; // Also decrements j. a[j] = temp; }    } }

where  is the length of the array. They would (hopefully) only use a while loop when necessary. Is there a specific reason that while loops are used?

Billnyethefrenchfry (talk) 23:59, 15 August 2023 (UTC)

 * Early pseudo code didn't use for loops, so it's common / traditional to use while loops. MrOllie (talk) 00:10, 16 August 2023 (UTC)

 * What do you mean by "early pseudocode"? Anything that I've seen written uses  loops in this case. Even if early examples of pseudocode didn't include   loops, we aren't writing early examples of pseudocode. Looking at the user that probably prompted the change's comment, they note that FORTRAN (and, in fact, most BASIC-like languages) use   loops like this:

do I = 0, n - 1 ! ... end do
 * Even if we don't want the weird FORTRAN  statement, and can't write C-like loops, we could still write it similar to a language like VBS:

Dim I For I = 0 To n - 1 ' ... Next
 * This reduces the clutter of the while loop while also being similar to an actual language. If it could be confusing to some people who didn't read the piece of text directly below the code snippet, a comment could be added. In any case, a while loop is not needed. From my understanding, pseudocode is meant to be used as a skeleton to base actual code off of, and is more useful when it resembles the code that will be based off it. Billnyethefrenchfry (talk) 03:29, 4 September 2023 (UTC)
 * Pseudocode is meant to be a human readable explanation of an algorithm, not a 'skeleton to base actual code off of'. It follows certain conventions (which vary a bit from author to author but are mostly consistent). We should not be arbitrarily adopting syntax peculiar to one language or another. Wikipedia in general is meant to educate newcomers to the topic, not to be a repository of code for programmers to cut and paste. MrOllie (talk) 03:50, 4 September 2023 (UTC)
 * That is a fair point, and I retract my statement of it being a "skeleton". However, a for-loop is (at least for me) more readable than a while loop. Rather than one having to piece together that it iterates over the whole array, it just tells you "loop through the indexes of the array". Billnyethefrenchfry (talk) 16:53, 4 September 2023 (UTC)
 * Simple for loops are arguably more readable, sure. But in this case one of the loops requires a compound conditional: while j >= 0 and A[j] > x. That does not amend itself to a for loop construction. And it is simpler for a newcomer to understand only one type of loop construction. MrOllie (talk) 17:08, 4 September 2023 (UTC)
 * If one were to pronounce "for I from 0 to upper bound of A, do a thing", it would be immediately intuitive that, for "I" from 0 to the upper bound of A, a thing would be done. The reason keywords have their names is so that they are simple for someone learning the language to grasp.
 * I agree with you that the compound conditional in the inner loop is much harder to represent than the outer loop of "for I from x to y", but there is no reason that we shouldn't use the simplest representation ("For I From 1 To length(A) - 1 ... Loop" or "For I From 1 To UBound(A) ... Loop") for the outer loop.
 * Billnyethefrenchfry (talk) 12:17, 3 October 2023 (UTC)
 * Sure, there is a reason. To repeat it: it is simpler for a newcomer to understand only one type of loop construction MrOllie (talk) 12:24, 3 October 2023 (UTC)

The example animation is flawed
If feel like nit picking but it just looked like there is something wrong with the animation, and I have to comment for correctness sake ;-).

It (the one with blue background and orange bars - i.e. File:Insertion_sort.gif) does work as in a demonstration on what insertion sort looks like. However, in the beginning a value appears which is not in the original unsorted array at all. The two "same values" from the beginning are not there during the sort, so a value is lost, and the very last value is also lost and just disappears - it is not there anymore when the sort finishes. However it looks like it is sorting correctly otherwise during the animation.

The plausible explanation I can come up with is simple - the example is missing the first (initial state) frame and the last frame! =). Adding an initial state where there are no two same values and one last write (write the stored value) everything lines up.

This is besides the point of an example / demonstration, but those who are keen on details might get confused on what is going on. Viileeditor (talk) 08:29, 26 September 2023 (UTC)

 * The fact is that it's incorrect, and the fact that there is an inconsistency with the first frame and first element of the list are enough to justify removal I think. There is no need to add a disclaimer about nit-picking, since the algorithms and all examples of this technical topic should be 100% correct. cperk (talk) 23:31, 14 October 2023 (UTC)

Recursive implementation?
What is the purpose of having the recursive implementation?

 * Special:Contributions/87.19.154.159 (January 2017)
 * Special:Diff/923556769 (October 2019)

Apart from not being cited to any source and looking like a boast of its author, proud of having understood recursion, it also does not make the article any better. The recursive approach is not simpler, not shorter and not faster than the iterative one, and it requires unacceptable amount of additional memory in the stack space. There are many ways to implement the algorithm worse than the original, but IMVHO popularizing them is not a mission of Wikipedia... --CiaPan (talk) 08:38, 29 December 2023 (UTC)

title: Talk:Insertion sort