Ускорить выполнение кода

        static void RemoveMas(ref int[] array, int index)
        {
            int[] newAr = new int[array.Length - 1];
            for (int i = 0; i < index; i++)
                newAr[i] = array[i];
            for (int i = index + 1; i < array.Length; i++)
                newAr[i - 1] = array[i];
            array = newAr;
        }
        static void Insert(ref int[] array, int value, int index)
        {
            int[] newAr = new int[array.Length + 1];
            newAr[index] = value;
            for (int i = 0; i < index; i++)
                newAr[i] = array[i];
            for (int i = index; i < array.Length; i++)
                newAr[i + 1] = array[i];
            array = newAr;
        }
        static void Add(ref int[] array, int value)
        {
            Insert(ref array, value, array.Length);
        }
 
 
        static void Main()
        {
            Console.ReadLine();
            string a = Console.ReadLine();
            int[] array = a.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries)
                            .Select(int.Parse)
                            .ToArray();
            int result = 0;
            int x = 0;
            int n = 0;
            while (array.Length > 2)
            {
                Array.Sort(array);
                n = array.Length;
                x = array[0] + array[n - 2];
                result += x;
                RemoveMas(ref array, n-2);
                RemoveMas(ref array, 0);
                Add(ref array, x);
            }
               
            result = result + array.Sum();
            
            Console.WriteLine(result);
 
        }

using System;
using System.Linq;
 
namespace CyberForum
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rand = new Random();
            // случайный массив на десять тысяч элементов
            int[] array = Enumerable.Range(0, 10000).OrderBy(i => rand.Next()).ToArray();
 
            int result = Foo(array);
            Console.WriteLine(result);
        }
 
        static int Foo(int[] arr)
        {
            int from = 0;
            int to = arr.Length;
            int result = 0;
 
            // единожды сортируем массив полностью 
            Sort(arr, from, to);
 
            while ((to - from) > 2)
            {
                //sort(a) // отсортировать массив по возрастанию элементов
                // (!) нет смысла сортировать весь массив, уже достаточно подсортировать только для последних элемента
                Sort(arr, to - 2, to);
 
                //n = size(a)
                int n = to - from;
 
                //x = a[0] + a[n - 2]
                int x = arr[from] + arr[to - 2];
 
                //result += x // добавить x в накапливаемому результату
                result += x;
 
                //delete(a, n - 2) // удалить элемент по индексу (n-2)
                arr[to - 2] = arr[to - 1];
 
                //add(a, x) // добавить элемент по значением x в конец массива
                arr[to - 1] = x;
 
                //delete(a, 0) // удалить элемент по индексу 0
                from++;
            }
 
            return result + Sum(arr, from, to);
        }
        static void Sort(int[] array, int from, int to)
        {
            for (int i = from; i < to; i++)
            {
                for (int j = i + 1; j < to; j++)
                {
                    if (array[i] > array[j])
                        (array[i], array[j]) = (array[j], array[i]);
                }
            }
        }
 
        static int Sum(int[] array, int from, int to)
        {
            int sumResult = 0;
 
            for (int i = from; i < to; i++)
                sumResult += array[i];
 
            return sumResult;
        }
    }
}