sortedp

This predicate just tests if the list is sorted. It does not sort or otherwise modify the list!

The notion of "sorted" only really applies to lists of numbers. It does not apply to lists of atoms.

A list is sorted if:

• it's null, or
• it has only one element, or
• the first element is less than or equal to the second element, and
  the rest of the list is sorted.

sort

A list is not an array. If you try to treat it as an array, using functions like setq and setf, you are only making things much more difficult for yourself. There's a reason I didn't teach these functions.

To insert an element into an already sorted list:

• If the element is less than or equal to the first element, just add the element to the front of the list;
• Else cons the car of the list onto the result of inserting the element into the cdr of the list.

To sort a list:

• If the list is empty or has only one element, then it is already sorted; just return it.
• Otherwise, sort the cdr of the list and use the above insert function to insert the car into it.

permutedp

This predicate just tests if one list is a permutation of the other. It does not sort or otherwise modify either list!

Note that (a b b c d) is a permutation of (a b b c d), and that (x y z) is not a permutation of (x x y z). There is only one correct definition of permutation, and this assignment uses it.

To remove one element from a list:

• If the car of the list is the atom to be removed, return the cdr of the list
• Otherwise, cons the car of the list onto the result of removing the element from the cdr of the list.

To test if one list is a permutation of the other

• If both lists are null, the result is true
• If one list is null but the other isn't, the result is false
• If the car of the first list is a member of the second list, then recur using
  • the cdr of the first list, and
  • the result of removing one copy of the car of the first list from the second list;
• Otherwise, the result is false (nil).