Objective

Implement a function that sorts an array of record by key, ascending, without ever reordering two records that carry the same key.

Steps

• The harness declares the type exactly like this, and your file has to declare it the same way: typedef struct s_record { int key; char label; } record;
• arr points at n records. Reorder them in place, smallest key first. Nothing is returned and nothing is allocated.
• Records that share a key must come out in the order they went in. That property has a name, stability, and it is the only thing this exercise grades beyond the key order.
• Your comparison never looks at label. It exists so the tests can tell which of two tied records landed first: the examples print the label of each record after the call, separated by single spaces. One test prints the keys on a first line and the labels on a second.
• An unstable sort gets the key order right and the label sequence wrong, which is a fail here. Selection sort reorders ties. So do heapsort and most quicksort variants. Insertion sort does not, and it needs no scratch buffer, which matters because you cannot allocate one.
• Running the sort a second time on its own output has to change nothing.
• Keys use the whole range of int, INT_MIN and INT_MAX included. Subtracting one key from another to compare them overflows, so compare the two values directly.
• Touch exactly the first n records. arr[n] and everything past it belongs to the caller.
• n of 0 and n of 1 are already sorted. Return without writing anything.
• You cannot call anything. Moving records around and comparing keys is your own code.

Objective

Implement a function that sorts an array of record by key, ascending, without ever reordering two records that carry the same key.

Steps

• The harness declares the type exactly like this, and your file has to declare it the same way: typedef struct s_record { int key; char label; } record;
• arr points at n records. Reorder them in place, smallest key first. Nothing is returned and nothing is allocated.
• Records that share a key must come out in the order they went in. That property has a name, stability, and it is the only thing this exercise grades beyond the key order.
• Your comparison never looks at label. It exists so the tests can tell which of two tied records landed first: the examples print the label of each record after the call, separated by single spaces. One test prints the keys on a first line and the labels on a second.
• An unstable sort gets the key order right and the label sequence wrong, which is a fail here. Selection sort reorders ties. So do heapsort and most quicksort variants. Insertion sort does not, and it needs no scratch buffer, which matters because you cannot allocate one.
• Running the sort a second time on its own output has to change nothing.
• Keys use the whole range of int, INT_MIN and INT_MAX included. Subtracting one key from another to compare them overflows, so compare the two values directly.
• Touch exactly the first n records. arr[n] and everything past it belongs to the caller.
• n of 0 and n of 1 are already sorted. Return without writing anything.
• You cannot call anything. Moving records around and comparing keys is your own code.