import java.util.*;

class ConfigRecord {

String key;

String value;

public ConfigRecord(String key, String value) {

this.key = key;

this.value = value;

}

@Override

public String toString() {

return "Key: " + key + ", Value: " + value;

}

}

public class MemoryEfficientConfigSorter {

public static List<ConfigRecord> sortConfigRecords(List<ConfigRecord> records) {

if (records == null || records.isEmpty()) {

return new ArrayList<>(); // Return empty list for null or empty input

}

// Use a simple insertion sort for memory efficiency.

// Insertion sort is good for small datasets and nearly sorted data.

List<ConfigRecord> sortedRecords = new ArrayList<>(records); // Create a copy to avoid modifying the original

for (int i = 1; i < sortedRecords.size(); i++) {

ConfigRecord current = sortedRecords.get(i);

int j = i - 1;

// Move elements of sortedRecords[0..i-1], that are greater than current,

// to one position ahead of their current position

while (j >= 0 && sortedRecords.get(j).key.compareTo(current.key) > 0) {

sortedRecords.set(j + 1, sortedRecords.get(j));

j--;

}

sortedRecords.set(j + 1, current);

}

return sortedRecords;

}

public static void main(String[] args) {

List<ConfigRecord> configRecords = new ArrayList<>();

configRecords.add(new ConfigRecord("setting3", "value3"));

configRecords.add(new ConfigRecord("setting1", "value1"));

configRecords.add(new ConfigRecord("setting2", "value2"));

configRecords.add(new ConfigRecord("setting4", "value4"));

List<ConfigRecord> sortedConfigRecords = sortConfigRecords(configRecords);

for (ConfigRecord record : sortedConfigRecords) {

System.out.println(record);

}

}

}