another C# solution -

ReverseShuffleMerge4.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ReverseShuffleMerge
{
    class Program
    {
        static void Main(string[] args)
        {
            string input = Console.ReadLine();

            int[] skip = new int[26];
            int[] add = new int[26];

            for (int i = 0; i < input.Length; i++)
            {
                skip[input[i] - 'a']++;
            }

            for (int i = 0; i < 26; i++)
            {
                skip[i] /= 2;
                add[i] = skip[i];
            }

            Stack<char> stack = new Stack<char>();
            for (int i = input.Length - 1; i >= 0; i--)
            {
                char ch = input[i];
                while(stack.Count > 0 && add[ch - 'a'] > 0 && stack.Peek() > ch && skip[stack.Peek() - 'a'] > 0)
                {
                    char chTop = stack.Pop();
                    add[chTop - 'a']++;
                    skip[chTop - 'a']--;
                }

                if (add[ch - 'a'] > 0)
                {
                    stack.Push(ch);
                    add[ch - 'a']--;
                }
                else
                {
                    skip[ch - 'a']--;
                }
            }

            string output = string.Empty;
            while(stack.Count > 0)
            {
                output = stack.Pop() + output;
            }

            Console.WriteLine(output);
        }
    }
}