Can't say this code 100% standard complaint, but it definitely exposes some bugs from every of these three compilers. Here's links to bug reports with minimized examples created from initial example, if interested:

1. MSVC
2. Clang
3. GCC

With regard to "fixes", MSVC already works pretty much. And @Jarod42 able to make Clang happy (Godbolt).

Here's working code for GCC (Godbolt):

#include <cstddef>
#include <concepts>
#include <utility>
#include <array>
#include <algorithm>

using Index = std::size_t;
using Alignment = std::size_t;
struct Key {
  Index old;
  Alignment a;
};

template<::Key k, typename T> struct Elem {};
template<typename ...Elems> struct Map : Elems... {};

template<typename ...Ts> struct Tuple {};
struct alignas(2) s_1 {};
struct alignas(2) s_2 {};
struct alignas(2) s_3 {};
struct alignas(2) s_4 {};
using T1 = Tuple<char, short, s_1, s_2, s_3, s_4, int, double>;




template<::Key...> struct Key_seq {};
template<auto array, auto len>
using Make_key_seq = decltype([]<auto ...Is>(std::index_sequence<Is...>&&){
  return ::Key_seq<array[Is]...>{};
}(std::make_index_sequence<len>{}));




template<typename ...Ts_>
consteval auto sort_tuple(::Tuple<Ts_...>&& tuple)
{

  constexpr auto size = []<typename ...Ts>(::Tuple<Ts...>&){
    return sizeof...(Ts);
  }(tuple);


  constexpr auto unsorted = []<
    typename ...Ts,
    auto ...Is
  >(::Tuple<Ts...>&, std::index_sequence<Is...>&&){
    return std::array<::Key, size>{::Key{Is, alignof(Ts)}...};
  }(tuple, std::make_index_sequence<size>{});


  constexpr auto sorted = [](auto unsorted){
    std::sort(
      unsorted.begin(), unsorted.end(),
      [](const auto& lhs, const auto& rhs){
        return lhs.a > rhs.a;
      }
    );
    return unsorted;
  }(unsorted);

  // changed this part, that now uses 'Make_key_seq'
  using Sorted = decltype([]<auto ...Keys, auto ...Is>(
    ::Key_seq<Keys...>&&,
    std::index_sequence<Is...>&&
  ){

    // needed to move it inside here, otherwise error
    using Unsorted = decltype([]<typename ...Ts>(::Tuple<Ts...>&){
      return ::Map<
        ::Elem<::Key{Is, alignof(Ts)}, Ts>...
      >{};
    }(tuple));

    return ::Tuple<
      decltype([]<::Key k, typename T>(
        [[maybe_unused]] ::Elem<k, T>&& deduced_by_comp
      ){
        return T{};
      }.template operator()<Keys>(Unsorted{}))...
    >{};

  }(::Make_key_seq<sorted, size>{}, std::make_index_sequence<size>{}));


  return Sorted{};
};
using Sorted = decltype(sort_tuple(T1{}));

using Correct = Tuple<double, int, short, s_1, s_2, s_3, s_4, char>;
static_assert(std::same_as<Correct, Sorted>);

auto main() -> int;