Help to decrese query time in huge table of 100M+ rows on Ms-SQL Server
To make this work well you need to create a separate query for each sort order, and have indexes that support the OFFSET .. FETCH without needing to sort the whole table first.  For the query part you can use IF statements with static SQL, or dynamic SQL.  Here's how to do this with some filtered indexes and dynamic SQL:

--drop table if exists users
go
create table users(id int primary key, name nvarchar(200), address nvarchar(200), city nvarchar(200), deleted_at datetime2 null)
go
create index ix_users_city on users(city) where deleted_at is null
create index ix_users_name on users(name) where deleted_at is null
create index ix_users_address on users(address) where deleted_at is null
go

CREATE OR ALTER PROCEDURE BaseUserIndex
    @Offset int,
    @Limit int,
    @SortCol int,
    @SortDir nvarchar(10),
    @Search nvarchar(255) = NULL
AS BEGIN
/*
  exec BaseUserIndex 0,100,2,'asc'
*/
    SET NOCOUNT ON;

    declare @sql nvarchar(max) = concat(N'
    SELECT id,
    name,
    address,
    city
    FROM users
    WHERE deleted_at IS NULL
    ORDER BY ',
        case 
        when (@SortCol = 0 and @SortDir='asc')  then N'name asc'
        when (@SortCol = 0 and @SortDir='desc') then N'name desc'
        when (@SortCol = 1 and @SortDir='asc')  then N'address asc'
        when (@SortCol = 1 and @SortDir='desc') then N'address desc'
        when (@SortCol = 2 and @SortDir='asc')  then N'city asc'
        when (@SortCol = 2 and @SortDir='desc') then N'city desc'
        end
        ,N'
    OFFSET ', @Offset, N' ROWS 
    FETCH NEXT ', @Limit, N' ROWS ONLY'
    )

    --print @sql
    exec ( @sql )

END