algorithm correctness

An algorithm is correct when it gives the right answer on every legal input — not most of the time, not on the cases you happened to test, but always. This is a high bar, and on purpose. A bridge that holds up under the trucks you tried but collapses under one you did not is not "mostly safe"; it is unsafe. Likewise an algorithm that sorts every list you tried but mangles one particular list is simply not a correct sorting algorithm.

Precisely, correctness means: for every input that meets the precondition (the assumed conditions on the input), the algorithm halts and its output satisfies the postcondition (the required relationship to the input that defines a right answer). Two things are bundled here — it must stop, and when it stops the output must be right. The standard way to actually establish this is not testing but reasoning, and the workhorse tool is the loop invariant: a statement that stays true every time around a loop. For insertion sort, the invariant is that the prefix A[1..i] is always in sorted order. It holds before the loop starts, because a one-element prefix is trivially sorted. Each pass inserts A[i+1] into its right place, so the now-longer prefix A[1..i+1] is sorted and the invariant survives the step. When the loop ends, i has reached n, so the sorted prefix is the whole array — which is exactly what we wanted. That chain of reasoning, not a pile of passing examples, is what proves correctness.

Why insist on proof rather than testing? Because most problems have infinitely many instances, so no finite test suite can cover them all; tests can reveal bugs but never their absence. Correctness also splits into two flavours worth naming: partial correctness says "if it halts, the answer is right," and total correctness adds "and it always halts." An algorithm can be partially correct yet loop forever on some input, which is useless in practice — so for a genuine guarantee you need both the right answer and termination.