Quicksort is one of the very popular sorting algorithm in programming, often used to sort large list of numbers. Though their are numerous algorithm available to sort list of objects, including integer, string and floating point number, quicksort is best for general purpose. It's a divide and conquer algorithm, where we divide the given array with respect to a particular element, known as 'pivot' such that the lower partition of the array are less than the pivot and upper partition elements of the array are higher than the pivot. Quicksort is also one of the best example of
recursion. It's naturally recursive, because it sort the large list by dividing into smaller sub-list and then applying same algorithm on those. Base case of recursion is when list contains either one or zero element, in that case they are sorted. Quicksort is well ahead with primitive sorting algorithms e.g. insertion sort, selection sort and
bubble sort. Average time complexity of quicksort is
O(nlogn), while in worst case it's performance is similar to bubble sort i.e.
O(n^2). Apparently worst case of quicksort is the best case of insertion sort, where they have to sort an already sorted list. In this article, we will learn
how to implement quicksort algorithm in Java using recursion. We will also learn how quicksort works, and how it sorts large list of unsorted number. In last section, we will see some important things about quicksort.