Hi Waghmare,
I have created a sample which full fill your requirement you need to modify the according to your need.
HTML
<asp:UpdatePanel runat="server">
    <ContentTemplate>
        <br />
        <br />
        <div>
            <asp:HiddenField ID="hfClassApplied" runat="server" />
            <asp:GridView ID="gvCustomers" runat="server" AutoGenerateColumns="false" AllowPaging="true"
                PageSize="5" OnPageIndexChanging="gvCustomers_PageIndexChanging" OnRowDataBound="RowDataBound">
                <Columns>
                    <asp:TemplateField>
                        <HeaderTemplate>
                            <asp:Label ID="lblCustomerID" Text="CustomerID" runat="server" />
                            <asp:TextBox ID="txtCustomerID" runat="server" AutoPostBack="true" OnTextChanged="TextChanged" />
                            <asp:LinkButton ID="lnkCustomerID" runat="server" OnClick="Sort" CssClass="glyphicon glyphicon-arrow-up"></asp:LinkButton>
                        </HeaderTemplate>
                        <ItemTemplate>
                            <asp:Label ID="Label2" Text='<%# Eval("CustomerID") %>' runat="server" />
                        </ItemTemplate>
                    </asp:TemplateField>
                    <asp:TemplateField>
                        <HeaderTemplate>
                            <asp:Label ID="lblCompanyName" Text="CompanyName" runat="server" />
                            <asp:TextBox ID="txtCompanyName" runat="server" AutoPostBack="true" OnTextChanged="TextChanged" />
                            <asp:LinkButton ID="lnkCompanyName" runat="server" OnClick="Sort" CssClass="glyphicon glyphicon-arrow-up"></asp:LinkButton>
                        </HeaderTemplate>
                        <ItemTemplate>
                            <asp:Label ID="Label1" Text='<%# Eval("CompanyName") %>' runat="server" />
                        </ItemTemplate>
                    </asp:TemplateField>
                    <asp:TemplateField>
                        <HeaderTemplate>
                            <asp:Label ID="lblContactName" Text="ContactName" runat="server" />
                            <asp:TextBox ID="txtContactName" runat="server" AutoPostBack="true" OnTextChanged="TextChanged" />
                            <asp:LinkButton ID="lnkContactName" runat="server" OnClick="Sort" CssClass="glyphicon glyphicon-arrow-up"></asp:LinkButton>
                        </HeaderTemplate>
                        <ItemTemplate>
                            <asp:Label ID="Label2" Text='<%# Eval("ContactName") %>' runat="server" />
                        </ItemTemplate>
                    </asp:TemplateField>
                    <asp:TemplateField>
                        <HeaderTemplate>
                            <asp:Label ID="lblCity" Text="City" runat="server" />
                            <asp:TextBox ID="txtCity" runat="server" AutoPostBack="true" OnTextChanged="TextChanged" />
                            <asp:LinkButton ID="lnkCity" runat="server" OnClick="Sort" CssClass="glyphicon glyphicon-arrow-up"></asp:LinkButton>
                        </HeaderTemplate>
                        <ItemTemplate>
                            <asp:Label ID="Label3" Text='<%# Eval("City") %>' runat="server" />
                        </ItemTemplate>
                    </asp:TemplateField>
                    <asp:TemplateField>
                        <HeaderTemplate>
                            <asp:Label ID="lblCountry" Text="Country" runat="server" />
                            <asp:TextBox ID="txtCountry" runat="server" AutoPostBack="true" OnTextChanged="TextChanged" />
                            <asp:LinkButton ID="lnkCountry" runat="server" OnClick="Sort" CssClass="glyphicon glyphicon-arrow-up"></asp:LinkButton>
                        </HeaderTemplate>
                        <ItemTemplate>
                            <asp:Label ID="Label4" Text='<%# Eval("Country") %>' runat="server" />
                        </ItemTemplate>
                    </asp:TemplateField>
                </Columns>
            </asp:GridView>
        </div>
    </ContentTemplate>
</asp:UpdatePanel>
C#
public string sortDirection
{
    get
    {
        return ViewState["sortDirection"] == null ? "ASC" : ViewState["sortDirection"].ToString(); // your default sort direction i.e. ASC.
    }
    set
    {
        ViewState["sortDirection"] = value;
    }
}
public string sortExpression
{
    get
    { 
        return ViewState["SortExpression"] == null ? "CustomerID" : ViewState["SortExpression"].ToString(); //Your by default sort expression. i.e. ColumnName
    }
    set
    {
        ViewState["SortExpression"] = value;
    }
}
string constr = ConfigurationManager.ConnectionStrings["constr"].ConnectionString;
protected void Page_Load(object sender, EventArgs e)
{
    if (!IsPostBack)
    {
        BindGrid();
    }
}
protected void RowDataBound(object sender, GridViewRowEventArgs e)
{
    if (e.Row.RowType == DataControlRowType.Header)
    {
        LinkButton lnkCustomerID = e.Row.FindControl("lnkCustomerID") as LinkButton;
        LinkButton lnkCompanyName = e.Row.FindControl("lnkCompanyName") as LinkButton;
        LinkButton lnkContactName = e.Row.FindControl("lnkContactName") as LinkButton;
        LinkButton lnkCity = e.Row.FindControl("lnkCity") as LinkButton;
        LinkButton lnkCountry = e.Row.FindControl("lnkCountry") as LinkButton;
        Label lblCustomerID = e.Row.FindControl("lblCustomerID") as Label;
        Label lblCompanyName = e.Row.FindControl("lblCompanyName") as Label;
        Label lblContactName = e.Row.FindControl("lblContactName") as Label;
        Label lblCity = e.Row.FindControl("lblCity") as Label;
        Label lblCountry = e.Row.FindControl("lblCountry") as Label;
        if (!string.IsNullOrEmpty(hfClassApplied.Value))
        {
            if (sortExpression == lblCustomerID.Text)
            {
                lnkCustomerID.CssClass = hfClassApplied.Value;
            }
            if (sortExpression == lblCompanyName.Text)
            {
                lnkCompanyName.CssClass = hfClassApplied.Value;
            }
            if (sortExpression == lblContactName.Text)
            {
                lnkContactName.CssClass = hfClassApplied.Value;
            }
            if (sortExpression == lblCity.Text)
            {
                lnkCity.CssClass = hfClassApplied.Value;
            }
            if (sortExpression == lblCountry.Text)
            {
                lnkCountry.CssClass = hfClassApplied.Value;
            }
        }
    }
}
public void BindGrid()
{
    using (SqlConnection con = new SqlConnection(constr))
    {
        using (SqlCommand cmd = new SqlCommand())
        {
            cmd.CommandText = "SELECT TOP 30 [CustomerID],[CompanyName],[ContactName],[City],[Country] FROM [Customers]";
            cmd.Connection = con;
            SqlDataAdapter sda = new SqlDataAdapter(cmd);
            DataTable dt = new DataTable();
            sda.Fill(dt);
            if (ViewState["GridView"] == null)
            {
                ViewState["GridView"] = dt;
            }
            gvCustomers.DataSource = ViewState["GridView"] as DataTable;
            gvCustomers.DataBind();
        }
    }
}
protected void gvCustomers_PageIndexChanging(object sender, GridViewPageEventArgs e)
{
    gvCustomers.PageIndex = e.NewPageIndex;
    SortGridView(sortExpression);
}
protected void Sort(object sender, EventArgs e)
{
    string assignedClass = (sender as LinkButton).CssClass.Split('-')[2];
    if (assignedClass.ToUpper() == "UP")
    {
        sortDirection = "ASC";
        hfClassApplied.Value = "glyphicon glyphicon-arrow-down";
    }
    else
    {
        sortDirection = "DESC";
        hfClassApplied.Value = "glyphicon glyphicon-arrow-up";
    }
    string selectedId = (sender as LinkButton).ID;
    Label lblCustomerID = (sender as LinkButton).FindControl("lblCustomerID") as Label;
    Label lblCompanyName = (sender as LinkButton).FindControl("lblCompanyName") as Label;
    Label lblContactName = (sender as LinkButton).FindControl("lblContactName") as Label;
    Label lblCity = (sender as LinkButton).FindControl("lblCity") as Label;
    Label lblCountry = (sender as LinkButton).FindControl("lblCountry") as Label;
    LinkButton lnkCustomerID = (sender as LinkButton).FindControl("lnkCustomerID") as LinkButton;
    LinkButton lnkCompanyName = (sender as LinkButton).FindControl("lnkCompanyName") as LinkButton;
    LinkButton lnkContactName = (sender as LinkButton).FindControl("lnkContactName") as LinkButton;
    LinkButton lnkCity = (sender as LinkButton).FindControl("lnkCity") as LinkButton;
    LinkButton lnkCountry = (sender as LinkButton).FindControl("lnkCountry") as LinkButton;
    if (lnkCustomerID.ID == selectedId)
    {
        sortExpression = lblCustomerID.Text;
    }
    if (lnkCompanyName.ID == selectedId)
    {
        sortExpression = lblCompanyName.Text;
    }
    if (lnkContactName.ID == selectedId)
    {
        sortExpression = lblContactName.Text;
    }
    if (lnkCity.ID == selectedId)
    {
        sortExpression = lblCity.Text;
    }
    if (lnkCountry.ID == selectedId)
    {
        sortExpression = lblCountry.Text;
    }
    SortGridView(sortExpression);
}
private void SortGridView(string sortExpression)
{
    DataTable dt = new DataTable();
    if (ViewState["GridView"] != null)
    {
        dt = ViewState["GridView"] as DataTable;
    }
    DataView dv = new DataView(dt);
    if (sortDirection == "ASC")
    {
        dv.Sort = sortExpression + " " + "ASC";
    }
    else
    {
        dv.Sort = sortExpression + " " + "DESC";
    }
    gvCustomers.DataSource = dv;
    gvCustomers.DataBind();
}
protected void TextChanged(object sender, EventArgs e)
{
    GridViewRow row = ((sender as TextBox).NamingContainer as GridViewRow);
    TextBox txtCustomerID = row.FindControl("txtCustomerID") as TextBox;
    TextBox txtCompanyName = row.FindControl("txtCompanyName") as TextBox;
    TextBox txtContactName = row.FindControl("txtContactName") as TextBox;
    TextBox txtCity = row.FindControl("txtCity") as TextBox;
    TextBox txtCountry = row.FindControl("txtCountry") as TextBox;
    string query = "SELECT [CustomerID],[CompanyName],[ContactName],[City],[Country] FROM [Customers]";
    string whereQuery = string.Empty;
    using (SqlConnection con = new SqlConnection(constr))
    {
        if (!string.IsNullOrEmpty(txtCustomerID.Text))
        {
            whereQuery += " CustomerID LIKE '" + txtCustomerID.Text.Trim() + "%'";
        }
        if (!string.IsNullOrEmpty(txtCompanyName.Text))
        {
            if (!string.IsNullOrEmpty(whereQuery))
            {
                whereQuery += " AND CompanyName LIKE '" + txtCompanyName.Text.Trim() + "%'";
            }
            else
            {
                whereQuery += " CompanyName LIKE '" + txtCompanyName.Text.Trim() + "%'";
            }
        }
        if (!string.IsNullOrEmpty(txtContactName.Text))
        {
            if (!string.IsNullOrEmpty(whereQuery))
            {
                whereQuery += " AND ContactName LIKE '" + txtContactName.Text.Trim() + "%'";
            }
            else
            {
                whereQuery += " ContactName LIKE '" + txtContactName.Text.Trim() + "%'";
            }
        }
        if (!string.IsNullOrEmpty(txtCity.Text))
        {
            if (!string.IsNullOrEmpty(whereQuery))
            {
                whereQuery += " AND City LIKE '" + txtCity.Text.Trim() + "%'";
            }
            else
            {
                whereQuery += " City LIKE '" + txtCity.Text.Trim() + "%'";
            }
        }
        if (!string.IsNullOrEmpty(txtCountry.Text))
        {
            if (!string.IsNullOrEmpty(whereQuery))
            {
                whereQuery += " AND Country LIKE '" + txtCountry.Text.Trim() + "%'";
            }
            else
            {
                whereQuery += " Country LIKE '" + txtCountry.Text.Trim() + "%'";
            }
        }
        whereQuery = !string.IsNullOrEmpty(whereQuery) ? " WHERE " + whereQuery : whereQuery;
        query += whereQuery;
        using (SqlCommand cmd = new SqlCommand(query, con))
        {
            SqlDataAdapter sda = new SqlDataAdapter(cmd);
            DataTable dt = new DataTable();
            sda.Fill(dt);
            if (dt.Rows.Count > 0)
            {
                if (ViewState["GridView"] != null)
                {
                    ViewState["GridView"] = dt;
                }
                gvCustomers.DataSource = ViewState["GridView"] as DataTable;
                gvCustomers.DataBind();
            }
            else
            {
                ScriptManager.RegisterClientScriptBlock(Page, this.GetType(), "Alert", "alert('No Records Found!!')", true);
            }
        }
    }
}
VB.Net
Public Property sortDirection() As String
	Get
			' your default sort direction i.e. ASC.
		Return If(ViewState("sortDirection") Is Nothing, "ASC", ViewState("sortDirection").ToString())
	End Get
	Set
		ViewState("sortDirection") = value
	End Set
End Property
Public Property sortExpression() As String
	Get
			'Your by default sort expression. i.e. ColumnName
		Return If(ViewState("SortExpression") Is Nothing, "CustomerID", ViewState("SortExpression").ToString())
	End Get
	Set
		ViewState("SortExpression") = value
	End Set
End Property
Private constr As String = ConfigurationManager.ConnectionStrings("constr").ConnectionString
Protected Sub Page_Load(sender As Object, e As EventArgs)
	If Not IsPostBack Then
		BindGrid()
	End If
End Sub
Protected Sub RowDataBound(sender As Object, e As GridViewRowEventArgs)
	If e.Row.RowType = DataControlRowType.Header Then
		Dim lnkCustomerID As LinkButton = TryCast(e.Row.FindControl("lnkCustomerID"), LinkButton)
		Dim lnkCompanyName As LinkButton = TryCast(e.Row.FindControl("lnkCompanyName"), LinkButton)
		Dim lnkContactName As LinkButton = TryCast(e.Row.FindControl("lnkContactName"), LinkButton)
		Dim lnkCity As LinkButton = TryCast(e.Row.FindControl("lnkCity"), LinkButton)
		Dim lnkCountry As LinkButton = TryCast(e.Row.FindControl("lnkCountry"), LinkButton)
		Dim lblCustomerID As Label = TryCast(e.Row.FindControl("lblCustomerID"), Label)
		Dim lblCompanyName As Label = TryCast(e.Row.FindControl("lblCompanyName"), Label)
		Dim lblContactName As Label = TryCast(e.Row.FindControl("lblContactName"), Label)
		Dim lblCity As Label = TryCast(e.Row.FindControl("lblCity"), Label)
		Dim lblCountry As Label = TryCast(e.Row.FindControl("lblCountry"), Label)
		If Not String.IsNullOrEmpty(hfClassApplied.Value) Then
			If sortExpression = lblCustomerID.Text Then
				lnkCustomerID.CssClass = hfClassApplied.Value
			End If
			If sortExpression = lblCompanyName.Text Then
				lnkCompanyName.CssClass = hfClassApplied.Value
			End If
			If sortExpression = lblContactName.Text Then
				lnkContactName.CssClass = hfClassApplied.Value
			End If
			If sortExpression = lblCity.Text Then
				lnkCity.CssClass = hfClassApplied.Value
			End If
			If sortExpression = lblCountry.Text Then
				lnkCountry.CssClass = hfClassApplied.Value
			End If
		End If
	End If
End Sub
Public Sub BindGrid()
	Using con As New SqlConnection(constr)
		Using cmd As New SqlCommand()
			cmd.CommandText = "SELECT TOP 30 [CustomerID],[CompanyName],[ContactName],[City],[Country] FROM [Customers]"
			cmd.Connection = con
			Dim sda As New SqlDataAdapter(cmd)
			Dim dt As New DataTable()
			sda.Fill(dt)
			If ViewState("GridView") Is Nothing Then
				ViewState("GridView") = dt
			End If
			gvCustomers.DataSource = TryCast(ViewState("GridView"), DataTable)
			gvCustomers.DataBind()
		End Using
	End Using
End Sub
Protected Sub gvCustomers_PageIndexChanging(sender As Object, e As GridViewPageEventArgs)
	gvCustomers.PageIndex = e.NewPageIndex
	SortGridView(sortExpression)
End Sub
Protected Sub Sort(sender As Object, e As EventArgs)
	Dim assignedClass As String = TryCast(sender, LinkButton).CssClass.Split("-"C)(2)
	If assignedClass.ToUpper() = "UP" Then
		sortDirection = "ASC"
		hfClassApplied.Value = "glyphicon glyphicon-arrow-down"
	Else
		sortDirection = "DESC"
		hfClassApplied.Value = "glyphicon glyphicon-arrow-up"
	End If
	Dim selectedId As String = TryCast(sender, LinkButton).ID
	Dim lblCustomerID As Label = TryCast(TryCast(sender, LinkButton).FindControl("lblCustomerID"), Label)
	Dim lblCompanyName As Label = TryCast(TryCast(sender, LinkButton).FindControl("lblCompanyName"), Label)
	Dim lblContactName As Label = TryCast(TryCast(sender, LinkButton).FindControl("lblContactName"), Label)
	Dim lblCity As Label = TryCast(TryCast(sender, LinkButton).FindControl("lblCity"), Label)
	Dim lblCountry As Label = TryCast(TryCast(sender, LinkButton).FindControl("lblCountry"), Label)
	Dim lnkCustomerID As LinkButton = TryCast(TryCast(sender, LinkButton).FindControl("lnkCustomerID"), LinkButton)
	Dim lnkCompanyName As LinkButton = TryCast(TryCast(sender, LinkButton).FindControl("lnkCompanyName"), LinkButton)
	Dim lnkContactName As LinkButton = TryCast(TryCast(sender, LinkButton).FindControl("lnkContactName"), LinkButton)
	Dim lnkCity As LinkButton = TryCast(TryCast(sender, LinkButton).FindControl("lnkCity"), LinkButton)
	Dim lnkCountry As LinkButton = TryCast(TryCast(sender, LinkButton).FindControl("lnkCountry"), LinkButton)
	If lnkCustomerID.ID = selectedId Then
		sortExpression = lblCustomerID.Text
	End If
	If lnkCompanyName.ID = selectedId Then
		sortExpression = lblCompanyName.Text
	End If
	If lnkContactName.ID = selectedId Then
		sortExpression = lblContactName.Text
	End If
	If lnkCity.ID = selectedId Then
		sortExpression = lblCity.Text
	End If
	If lnkCountry.ID = selectedId Then
		sortExpression = lblCountry.Text
	End If
	SortGridView(sortExpression)
End Sub
Private Sub SortGridView(sortExpression As String)
	Dim dt As New DataTable()
	If ViewState("GridView") IsNot Nothing Then
		dt = TryCast(ViewState("GridView"), DataTable)
	End If
	Dim dv As New DataView(dt)
	If sortDirection = "ASC" Then
		dv.Sort = (sortExpression & Convert.ToString(" ")) + "ASC"
	Else
		dv.Sort = (sortExpression & Convert.ToString(" ")) + "DESC"
	End If
	gvCustomers.DataSource = dv
	gvCustomers.DataBind()
End Sub
Protected Sub TextChanged(sender As Object, e As EventArgs)
	Dim row As GridViewRow = TryCast(TryCast(sender, TextBox).NamingContainer, GridViewRow)
	Dim txtCustomerID As TextBox = TryCast(row.FindControl("txtCustomerID"), TextBox)
	Dim txtCompanyName As TextBox = TryCast(row.FindControl("txtCompanyName"), TextBox)
	Dim txtContactName As TextBox = TryCast(row.FindControl("txtContactName"), TextBox)
	Dim txtCity As TextBox = TryCast(row.FindControl("txtCity"), TextBox)
	Dim txtCountry As TextBox = TryCast(row.FindControl("txtCountry"), TextBox)
	Dim query As String = "SELECT [CustomerID],[CompanyName],[ContactName],[City],[Country] FROM [Customers]"
	Dim whereQuery As String = String.Empty
	Using con As New SqlConnection(constr)
		If Not String.IsNullOrEmpty(txtCustomerID.Text) Then
			whereQuery += " CustomerID LIKE '" + txtCustomerID.Text.Trim() + "%'"
		End If
		If Not String.IsNullOrEmpty(txtCompanyName.Text) Then
			If Not String.IsNullOrEmpty(whereQuery) Then
				whereQuery += " AND CompanyName LIKE '" + txtCompanyName.Text.Trim() + "%'"
			Else
				whereQuery += " CompanyName LIKE '" + txtCompanyName.Text.Trim() + "%'"
			End If
		End If
		If Not String.IsNullOrEmpty(txtContactName.Text) Then
			If Not String.IsNullOrEmpty(whereQuery) Then
				whereQuery += " AND ContactName LIKE '" + txtContactName.Text.Trim() + "%'"
			Else
				whereQuery += " ContactName LIKE '" + txtContactName.Text.Trim() + "%'"
			End If
		End If
		If Not String.IsNullOrEmpty(txtCity.Text) Then
			If Not String.IsNullOrEmpty(whereQuery) Then
				whereQuery += " AND City LIKE '" + txtCity.Text.Trim() + "%'"
			Else
				whereQuery += " City LIKE '" + txtCity.Text.Trim() + "%'"
			End If
		End If
		If Not String.IsNullOrEmpty(txtCountry.Text) Then
			If Not String.IsNullOrEmpty(whereQuery) Then
				whereQuery += " AND Country LIKE '" + txtCountry.Text.Trim() + "%'"
			Else
				whereQuery += " Country LIKE '" + txtCountry.Text.Trim() + "%'"
			End If
		End If
		whereQuery = If(Not String.IsNullOrEmpty(whereQuery), Convert.ToString(" WHERE ") & whereQuery, whereQuery)
		query += whereQuery
		Using cmd As New SqlCommand(query, con)
			Dim sda As New SqlDataAdapter(cmd)
			Dim dt As New DataTable()
			sda.Fill(dt)
			If dt.Rows.Count > 0 Then
				If ViewState("GridView") IsNot Nothing Then
					ViewState("GridView") = dt
				End If
				gvCustomers.DataSource = TryCast(ViewState("GridView"), DataTable)
				gvCustomers.DataBind()
			Else
				ScriptManager.RegisterClientScriptBlock(Page, Me.[GetType](), "Alert", "alert('No Records Found!!')", True)
			End If
		End Using
	End Using
End Sub
ScreenShot
