Merge lists
to continue. (After that any entries made into the worksheet will be automatically saved, and you can re-load the partially-completed worksheet in future - at which point you will be asked to auto-save it again).
Enter your name:

### Preliminaries

- Set the browser to Full Screen view, to give this worksheet, and your code, as much space as possible.
- Remember that if the code editor has a tinted background it does not have focus and will not respond to edits. To give it focus click within the editor. (If a program is running, you will need to stop it first.)
- Use the auto-completion options as much as possible, because this reduces errors.
- Use the Hints only when you need them - as all use of hints is recorded. Use of Help is encouraged and not recorded.

Preliminaries completed

### Step 1: Getting started

From the Demo menu, access the Merge lists code, then select File > Auto Save and complete the dialog to ensure that your code is always saved. Remember that you can use the Undo button (or Ctrl-z) to undo recent changes.

Note that the code it containsa function merge, and one test for this function covering multiple test cases (assert instructions). The asserts are all all failing with the message: actual: [x]. Looking at the code for the merge it is not hard to see why: this is merely a 'skeletal' implementation: sufficient code only to compile, not to run correctly. Your task is to implement merge properly. Your implementation should:

- assume that both of the input lists, passed in as parameters a and b
- return a list, also in alphabetical order, that includes all elements from boths lists
- be recursive
- result in all tests passing (without modifying those tests)

Hint 1: Recursion

- Writing a recursive function means that in one or more places within your implementation of merge you will have an expression that itself makes use of the merge function - typically with a smaller, or simpler, version of the problem of the list.
- One of the first things to consider when writing a recursive function is the 'boundary' (or 'exit' or 'edge' condition) i.e. the specific condition(s) under which you have, or can derive, the result without needing to use sort recursively.

Hint 2: Getting started

The following is generic advice for writing a function where there might be more than one path to the result:

- start by defining a variable named result and then returing result at the end of the function. (Elan deliberately does not permit you to return from multiple places in a function - or a procedure - because that breaks the principles of structured programming.)
- result needs to be initialised with a value of the correct type, as defined in the signature of the merge function. This could be an empty List of the correct type.

Hint 3: Description of the algorithm

- If either of the input lists is empty (has length 0) then the result is just the other list.
- Otherwise, get hold of the first element in each list and compare them alphabetically. The result may then be contained by combining the

Hint 4: Some useful coding idioms and hints

- Define a variable only where the named value must later be re-assigned. In all other cases, define a named value with a let.
- The method length - called as a 'dotted' method on a named value holding a list returns its length as an integer.
- You can use a 'range index' to extract a part of a list as a new list of the same type. For example myList[3..7] will extract the members at indexes 3, 4, 5, and 6 (the upper bound is exclusive) - but remembed that you can use named values for either or both of those bounds.
- Indexes for lists (like arrays) always start from 0.
- To calculate the index for the mid-point of this list, use integer division to divide the length by two: div 2, rather than / 2. Think: why is that distinction important?

Hint 5: Suggested structure
A complete solution can consist only of these instructions. However, it is not necessarily wrong to use more instructions if you choose to. function sort(li as List<of String>) returns List<of String> variable ... let ... if ... let ... let ... let ... set ... end if return ... end function Enter each of these instructions, leaving all the fields empty and then try to work out - with careful reference to Hints 3 & 4, what should go into each field.
Hint 6: First fields shown
This code shows the first field of each instruction completed. function sort(li as List<of String>) returns List<of String> variable result set to ... let len be ... if len > 1 then let mid be ... let frontHalf be ... let backHalf be ... set result to ... end if return result end function
Hint 7: Method calls shown
This code now shows methods that are called in the remaining expression fields, but does not show the arguments that must be passed into them. function sort(li as List<of String>) returns List<of String> variable result set to li let len be li. ... if len > 1 then let mid be len ... let frontHalf be sort... let backHalf be sort... set result to merge... end if return result end function
Hint 8: The complete solution
You can still gain some marks by correctly copying this code into the editor and showing that the tests now all pass. With careful reference to Hints 3 & 4, try to work out the correct arguments. function sort(li as List<of String>) returns List<of String> variable result set to li let len be li.length() if len > 1 then let mid be len div 2 let frontHalf be sort(li[..mid]) let backHalf be sort(li[mid..]) set result to merge(frontHalf, backHalf) end if return result end function
Step completed Total hints used: /
Worksheet completed.
This worksheet is copyright © Richard Pawson 2025, and protected by the Creative Commons license: Attribution-NonCommercial-NoDerivatives 4.0 International. If you copy and modify this worksheet you may not distribute your modified version (outside your own teaching institution) without the author's permission. Please email the author to report errors or suggest improvements.