IOSP Kata: merge two sorted arrays without iterators

Question

I wrote the code below as a Kata to practice the Integration Operation Segregation Principle (IOSP, clean-code-developers.com). I would like to have some feedback on the code wrt. IOSP.

I know that the code is not as efficient as it could be (mostly due to the fact that I am generating some copies of Lists), but as I said: the focus of the Kata is IOSP, not efficiency.

---

Acceptance criteria:

• Method merge(...):
  • takes two (possibly null or empty), sorted Lists of some T extends Comparable<T>
    • If either of the input-Lists is null, it should be treated as empty list
  • returns a single List, containing all elements of the two input lists, that is also sorted
• The method should be pure, i.e.:
  • it must not throw any exception, and
  • the input-Lists should not be modified
• Method merge(...) does not need to be stable.

---

Implementation:

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.concurrent.ConcurrentHashMap;
class SortedListMerger<T extends Comparable<T>> {
 private static final ConcurrentHashMap<Class<?>, SortedListMerger<?>> instanceMap
 = new ConcurrentHashMap<>();
 @SuppressWarnings("unchecked")
 public static <T extends Comparable<T>> SortedListMerger<T> getInstance(Class<T> clazz) {
 return (SortedListMerger<T>) instanceMap.computeIfAbsent(
 clazz,
 unused -> new SortedListMerger<T>());
 }
 private SortedListMerger() {
 }
 public List<T> merge(List<? extends T> lhs, List<? extends T> rhs) {
 final MergeResult<T> mergeResult = mergeLists(lhs, rhs);
 return appendRest(mergeResult);
 }
 private MergeResult<T> mergeLists(List<? extends T> lhs, List<? extends T> rhs) {
 final List<? extends T> safeLhs = Optional.ofNullable(lhs).orElseGet(List::of);
 final List<? extends T> safeRhs = Optional.ofNullable(rhs).orElseGet(List::of);
 final int lhsSize = safeLhs.size();
 final int rhsSize = safeRhs.size();
 ArrayList<T> merged = new ArrayList<>(lhsSize + rhsSize);
 int lhsIndex = 0;
 int rhsIndex = 0;
 while (lhsIndex < lhsSize && rhsIndex < rhsSize) {
 final T lhsValue = safeLhs.get(lhsIndex);
 final T rhsValue = safeRhs.get(rhsIndex);
 if (lhsValue.compareTo(rhsValue) <= 0) {
 merged.add(lhsValue);
 ++lhsIndex;
 } else {
 merged.add(rhsValue);
 ++rhsIndex;
 }
 }
 return new MergeResult<>(safeLhs, lhsIndex, safeRhs, rhsIndex, merged);
 }
 private List<T> appendRest(MergeResult<T> result) {
 final List<T> intermediate = appendRest(
 result.safeLhs(),
 result.lhsIndex(),
 result.merged());
 return appendRest(result.safeRhs(), result.rhsIndex(), intermediate);
 }
 private List<T> appendRest(List<? extends T> from, int firstIndexOfRest, List<T> to) {
 List<T> result = new ArrayList<>(to);
 int index = firstIndexOfRest;
 while (index < from.size()) {
 result.add(from.get(index));
 ++index;
 }
 return result;
 }
 private record MergeResult<T extends Comparable<T>>(
 List<? extends T> safeLhs,
 int lhsIndex,
 List<? extends T> safeRhs,
 int rhsIndex,
 List<T> merged) {
 private MergeResult(
 List<? extends T> safeLhs,
 int lhsIndex,
 List<? extends T> safeRhs,
 int rhsIndex,
 List<T> merged) {
 this.safeLhs = List.copyOf(safeLhs);
 this.lhsIndex = lhsIndex;
 this.safeRhs = List.copyOf(safeRhs);
 this.rhsIndex = rhsIndex;
 this.merged = List.copyOf(merged);
 }
 }
}

---

In case you want to run the code, here are some manual tests:

class Main {
 public static void main(String[] args) {
 final SortedListMerger<Integer> merger = SortedListMerger.getInstance(Integer.class);
 System.out.println(merger.merge(null, null));
 System.out.println(merger.merge(List.of(), null));
 System.out.println(merger.merge(null, List.of()));
 System.out.println(merger.merge(List.of(), List.of()));
 System.out.println(merger.merge(null, List.of(0, 1, 3, 5, 7, 9, 11)));
 System.out.println(merger.merge(List.of(), List.of(0, 1, 3, 5, 7, 9, 11)));
 System.out.println(merger.merge(List.of(0, 2, 4, 6), null));
 System.out.println(merger.merge(List.of(0, 2, 4, 6), List.of()));
 System.out.println(merger.merge(List.of(0, 2, 4, 6), List.of(0, 1, 3, 5, 7, 9, 11)));
 }
}

Answer 1

Mixed concerns

Rather than just letting the client create instances of the SortedListMerger class, there's a private constructor and a singleton map construction mechanic.

If you really need to be able to construct the merger, based around the runtime class information then consider moving this responsibility out to a different class. This would allow the merger to concentrate on merging and the new class to concentrate on construction.

If you don't actually need to be able to construct instances based on the .class information, consider if you really need to create an instance at all. Changing the signature of the method to:

public static <S extends Comparable<S>> List<S> merge(List<? extends S> lhs, 
 List<? extends S> rhs) 

Simplifies it for the caller, since it's possible for the compiler to infer the necessary types:

System.out.println(SortedListMerger.merge(List.of(0, 2, 4, 6), 
 List.of(0, 1, 3, 5, 7, 9, 11)));

Testing

Rather than printing the output of the merge to the console, consider writing actual unit tests. This would allow the reader to know what to expect from the method call. When merging '0,1,2' and '1,3,4' do I expect '0,1,2,3,4' or '0,1,1,2,3,4' for example? Without seeing the expected output, it's a run-it and see situation, particularly since none of your examples had any duplicates in the source data.

There's an assumption in the code that sorted means in ascending order, however this doesn't seem to be explicitly stated in the requirements or method names. To me '4,3,2' is still sorted, it's just sorted the other direction. Consider if you want to support this, or make it more explicit that the sort direction must be ascending (maybe this is subjective since you're doing it the same what that sorted would).

Readability

I didn't find the code particularly easy to read. It felt overly complex, for the task that it's solving. Part of that is because the method names didn't really seem to necessarily convey what the methods were doing. So, looking at this Integration method:

public List<T> merge(List<? extends T> lhs, List<? extends T> rhs) {
 final MergeResult<T> mergeResult = mergeLists(lhs, rhs);
 return appendRest(mergeResult);
}

At first glance it seems like it could be reasonable. But on reflection, you've got:

1. Merge the lists.
2. Append the rest.

Ok, but if 1 has merged the lists, then what 'rest' is there to append? It turns out that 'merge list' really means merge until you've merged everything from one side or the other, then stop. If I drill into append the rest, it actually calls append the rest twice inside, once for the lhs and once for the rhs.

A similar thing could have been achieved at the end of the mergeLists method:

 merged.addAll(safeLhs.subList(lhsIndex, lhsSize));
 merged.addAll(safeRhs.subList(rhsIndex, rhsSize));

Which would have removed the need for the MergeResult etc. Whilst the logic has been split, it doesn't actually seem to have been split in a way that makes the code easier to understand.