QuickSort에 이용되는 Partition 기능을 이용하여, 특정 Pivot의 위치(m)를 구한 후, 이 인덱스 m 이 배열의 중간에 위치하는지 체크하고, 만약 중간값 N/2 보다 작으면, m+1 부터 마지막 배열요소 중에 중간값이 있는 것이므로, 다시 Recursion을 이용해 m+1 ~ N 배열요소들을 가지고 Partition을 실행한다. 이렇게 반복적으로 실행하면 중간값을 만나게 되고 이 요소를 리턴한다.

class FindMedianWithoutSort
{
    private int[] A = new int[]{ 1, 9, 5, 3, 8, 4, 2, 6, 7 };
        
    public void RunTest()
    {
        int answer = FindMedian();
        Console.WriteLine(answer);
    }

    int FindMedian()
    {
        int k = (int)Math.Ceiling((double)A.Length / 2);
        return FindKthSmallest(0, A.Length -1 , k -1);
    }

    int FindKthSmallest(int left, int right, int kth)
    {
        while (true)
        {
            int m = Partition(left, right);

            if (m == kth)
            {
                return A[m];
            }
            else if (m < kth)
            {
                left = m + 1;                    
            }
            else
            {
                right = m - 1;
            }
        }
    }

    int Partition(int left, int right)
    {            
        int pivot = A[right];            
        int i = left;
        int j = right - 1;

        while(i < j)
        {
            while (i < right && A[i] <= pivot) i++;
            while (j >= 0 && A[j] >= pivot) j--;

            if (i < j)
            {
                //ref를 사용하여 pass by reference
                Swap(ref A[i], ref A[j]);
            }
        }

        Swap(ref A[i], ref A[right]);
        return i;
    }

    void Swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
}

보다 일반적인 케이스인 k번째 작은 배열요소는 위의 FindKthSmallest()를 호출하여 구할 수 있다.