Insertion (1)
Problem: Given a (sub)array a[left…right], insert a value val at a[ins]. If necessary, shift values right to make way for it.
Array insertion algorithm:
To insert val at index ins in a[left…right] (where left ? ins ? right):
1. Copy a[ins…right–1] into a[ins+1…right].2. Copy val into a[ins].3. Terminate.