Insertion Sort LEGEND: ! mark to the left of which the array is sorted | placeholder for above mark while invariant may be temporarily violated > pointer to pair of items that will be swapped if out of order B ! E W I L D E R M E N T > B | E W I L D E R M E N T B E ! W I L D E R M E N T B > E | W I L D E R M E N T B E W ! I L D E R M E N T B E > W | I L D E R M E N T B > E I | W L D E R M E N T B E I W ! L D E R M E N T B E I > W | L D E R M E N T B E > I L | W D E R M E N T B E I L W ! D E R M E N T B E I L > W | D E R M E N T B E I > L D | W E R M E N T B E > I D L | W E R M E N T B > E D I L | W E R M E N T > B D E I L | W E R M E N T B D E I L W ! E R M E N T B D E I L > W | E R M E N T B D E I > L E | W R M E N T B D E > I E L | W R M E N T B D > E E I L | W R M E N T B D E E I L W ! R M E N T B D E E I L > W | R M E N T B D E E I > L R | W M E N T B D E E I L R W ! M E N T B D E E I L R > W | M E N T B D E E I L > R M | W E N T B D E E I > L M R | W E N T B D E E I L M R W ! E N T B D E E I L M R > W | E N T B D E E I L M > R E | W N T B D E E I L > M E R | W N T B D E E I > L E M R | W N T B D E E > I E L M R | W N T B D E > E E I L M R | W N T B D E E E I L M R W ! N T B D E E E I L M R > W | N T B D E E E I L M > R N | W T B D E E E I L > M N R | W T B D E E E I L M N R W ! T B D E E E I L M N R > W | T B D E E E I L M N > R T | W B D E E E I L M N R T W !