Kth Largest Element

Given an unsorted array, find the k-th largest element. Implement an algorithm to solve this problem and provide time complexity analysis. Provide more than three test cases. The array may contain duplicates and negative numbers, with a length of up to 10^5, and k may be greater than the array length. Example Input 6 2 3 2 1 5 6 4