Skip to main content
Back to ChallengesImplement Quick SortMedium 30 min

Implement Quick Sort

Write a function that takes in an array of integers and returns a sorted version of that array using the Quick Sort algorithm.

Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

Examples

Input: arr = [8, 5, 2, 9, 5, 6, 3]
Output: [2, 3, 5, 5, 6, 8, 9]
The array is sorted in ascending order.

Constraints

  • • 1 <= arr.length <= 10^5
  • • -10^4 <= arr[i] <= 10^4

Complexity Analysis

Time
O(N log N) on average, O(N^2) in the worst case (e.g. sorted array with poor pivot).
Space
O(log N)
recursion stack depth.

Test Cases

#1 Standard unsorted array
Input: arr = [8,5,2,9,5,6,3]
Expected: [2,3,5,5,6,8,9]
#2 Already sorted array
Input: arr = [1,2,3,4,5]
Expected: [1,2,3,4,5]
JavaScript
Output
Click "Run Code" to see output here...