Do not use lambda functions when there’s builtin ones for the job. Also never use the cmp argument of sorted because it’s deprecated:
sorted(s, key=str.lower)
or
sorted(s, key=str.upper)
But that may not keep ‘A’ and ‘a’ in order, so:
sorted(sorted(s), key=str.upper)
that will and, by the nature of sorted the operation will be very fast for almost sorted lists (the second sorted).