Why is my implementation of QuickSort so slow and how can I make it better?

Question

Here's my quicksort working on a List, it's supposed to read from a large .txt file containing one number per line. After filling up the List from the file I tried to sort it, but for some reason it's taking way too long.

    // Main.cs
            List<int> myList = new List<int>();


            string[] lines = System.IO.File.ReadAllLines("largeFile.txt");

            foreach (string num in lines)
                myList.Add(int.Parse(num));
 

            QuickSort(ref myList, 0, myList.Count - 1);

quick.cs:

        static void Swap(List<int> myList, int indexA, int indexB)
        {
            int tmp = myList[indexA];
            myList[indexA] = myList[indexB];
            myList[indexB] = tmp;
        }

        static int Partition(ref List<int> myList, int leftIdx, int rightIdx)
        {
            int pivot = leftIdx - 1;

            for (int i = leftIdx; i < rightIdx; ++i)
            {
                if (myList[i] < myList[rightIdx])
                {
                    ++pivot;
                    Swap(myList, pivot, i);
                    
                }
            }

            ++pivot;
            Swap(myList, pivot, rightIdx);
            return pivot;
        }

        static void QuickSort(ref List<int> myList, int leftIdx, int rightIdx)
        {

            if (rightIdx <= leftIdx)
                return;

            int pivotIdx = Partition(ref myList, leftIdx, rightIdx);

            QuickSort(ref myList, leftIdx, pivotIdx - 1);
            QuickSort(ref myList, pivotIdx + 1, rightIdx);

            return;
        }

Compared to List.Sort() (which sorts it almost immediately) this is ridiculously slow, how can I improve this? For instance List.Sort takes 3 milliseconds while my method takes 14769

Answer 1

Example code for classic Lomuto partition scheme. It swaps middle element with last element which is then used as the pivot. Recurse on smaller, loop on larger reduces stack space to O(log(n)), but worst case time complexity remains at O(n^2).

        static public void QuickSort(int [] a, int lo, int hi)
        {
            while (lo < hi){
                int t;
                int p = a[(lo+hi)/2];           // use mid point for pivot
                a[(lo+hi)/2]= a[hi];            // swap with a[hi]
                a[hi] = p;
                int i = lo;
                for (int j = lo; j < hi; ++j){  // Lomuto partition
                    if (a[j] < p){              //  if a[j] < pivot
                        t = a[i];               //   swap a[i], a[j]
                        a[i] = a[j];
                        a[j] = t;
                        ++i;                    //   i += 1
                    }
                }
                t = a[i];                       // swap a[i], a[hi]
                a[i] = a[hi];                   //  to put pivot in place
                a[hi] = t;
                if(i - lo <= hi - i){           // recurse on smaller partiton
                    QuickSort(a, lo, i-1);      //   loop on larger
                    lo = i+1;
                } else {
                    QuickSort(a, i+1, hi);
                    hi = i-1;
                }
            }
        }