Which one of the given sorting techniques does not change the relative order of elements...

A stable sort preserves the relative order of elements with equal keys. Insertion sort is a stable sorting algorithm because it only shifts elements to the right during insertion, maintaining the original order of equal elements. Quick sort, selection sort, and heap sort are all unstable sorts—they may rearrange equal elements.

Step-by-step Derivation:
Stability in sorting refers to whether equal elements maintain their original relative order after sorting.

1. Insertion Sort: Compares elements one-by-one and inserts each into its correct position among already-sorted elements. Equal elements are never swapped past each other → STABLE.

2. Quick Sort: Uses partitioning around a pivot. Elements can be rearranged across partitions unpredictably → UNSTABLE.

3. Selection Sort: Finds the minimum/maximum and swaps it with the current position. This can move equal elements around → UNSTABLE.

4. Heap Sort: Builds a heap and repeatedly extracts the root. The heap structure can reorder equal elements → UNSTABLE.

Example: Sorting [(3,a), (1,b), (3,c), (2,d)] by first element:

• Insertion Sort result: (1,b), (2,d), (3,a), (3,c) — 3's maintain order ✓
• Heap Sort result: (1,b), (2,d), (3,c), (3,a) — 3's order reversed ✗

Answer: C) Insertion sort is the only stable algorithm among these four.