Here's a shorter merge sort, bottom up, called s. ((:[])<$>) divides up the list into singletons (turning "Joe" into ["J","o","e"]). d merges adjacent pairs of lists, using the basic merge function !. f iterates d until there's only one list.

Merge sort, 99 bytes

s=f.((:[])<$>)
a@(x:y)!b@(z:w)|x>z=z:a!w|0<1=x:y!b
a!b=a++b
d(x:y:z)=x!y:d z
d p=p
f[x]=x
f x=f$d x

Try it online!

Haskell, 57 56 37 33 bytes

f l=[y|x<-[minBound..],y<-l,y==x]

Feed it with Ints, e.g. f [1::Int,2,3].

A port of my answer from the other sort without builtin challenge which supports also lists with repeated values.

Edit: @Ørjan Johansen saved 4 bytes. Thanks!

Quicksort (sort of), 44 bytes

s(h:t)=s[e|e<-t,e<=h]++h:s[e|e<-t,e>h]
s x=x

Try it online!

How it works:

s(h:t)=               -- let h be the head and t the rest of the input list
        [e|e<-t,e<=h] -- take all elements e from t that are less or equal than h
       s              -- and sort them recursively
          ++ h :      -- append h and append
        [e|e<-t,e>h]  -- all elements from t greater than h
       s              -- after sorting them
s x=x                 -- base case: if there's no first elemet, i.e. the list
                      -- is empty, the result is also the empty list

Mergesort, 110 bytes

x@(a:r)#y@(b:s)|a<b=a:r#y|1<3=b:x#s
r#s=r++s
(x:r)!(a,b)=r!(b,x:a)
_!t=t
s[x]=[x]
s l|(a,b)<-l!([],[])=s a#s b

Try it online! Example usage: s [4,1,26,-3,0,5].

# takes two sorted lists and merges them. ! splits a list in two sublists of equal length. s returns singleton lists unchanged because they are already sorted and sorts longer lists by splitting them in two parts, recursively sorts both and merges the resulting lists.

Insertion Sort, 44 bytes

s!(a:b)|a<s=a:s!b
s!x=s:x
f(a:x)=a!f x
f a=a

Try it online!

Since nimi has already outgolfed me I thought I would post the solution I came up with to my own challenge.

Explanation

Here we define a function (!) that takes a sorted list and inserts an element so that the list is still sorted.

s!(a:b)|a<s=a:s!b
s!x=s:x

We then define a function f that takes sieves the elements of a list into this function. (basically the equivalent of a foldr).

f(a:x)=a!f x
f a=a

Since the empty list is sorted, and each insertion keeps the list sorted, the end result is a sorted list with all the same items as the original. This algorithm is O(n²).