申論題

二、快速排序法（quick sort）在處理一個含有 n 個元素的陣列的步驟如下： 步驟 1：先檢查是否只剩下一個元素，如果是的話，就 return，不需再做以下的步驟。 如果不是的話，就需再執行以下的步驟 2 至步驟 4。 步驟 2 ：先找一個指標（通常是第一個數），將陣列中所有 n 個元素，小於或等於 這個指標的數，都放在左邊的子集合中，反之則放在右邊的子集合中。 步驟 3：分別遞迴排序左邊的子集合及右邊的子集合。 步驟 4：結合左邊的子集合及右邊的子集合，即成為單一陣列。

⑶請問快速排序法在處理一個含有 n 個元素的陣列時，其最壞狀況的時間複雜度 （worst-case time complexity）為何？（5 分）