Trusted answers to developer questions

NlogN sorting algorithms

Get the Learn to Code Starter Pack

Break into tech with the logic & computer science skills you’d learn in a bootcamp or university — at a fraction of the cost. Educative's hand-on curriculum is perfect for new learners hoping to launch a career.

There are several sorting algorithms; each one has a different best and worst-case time complexity and is optimal for a particular type of data structure. Let’s look at some of the sorting algorithms that have a best-case or average-case time complexity of O(n log(n))O(n \ log (n)).

Merge Sort

Merge sort is a classic example of a divide-and-conquer algorithm. It has a guaranteed running time complexity of O(n log(n))O(n \ log (n)) in the best, average, and worst case. It essentially follows two steps:

  1. Divide the unsorted list into sub-lists until there are NN sub-lists with one element in each (NN is the number of elements in the unsorted list).
  2. Merge the sub-lists two at a time to produce a sorted sub-list; repeat this until all the elements are included in a single list.

Read up on how to implement a merge sort algorithm here.

HeapSort

Heapsort uses the heap data structure for sorting. The largest (or smallest) element is extracted from the heap (in O(1)O(1) time), and the rest of the heap is re-arranged such that the next largest (or smallest) element takes O(logn)O(log n) time. Repeating this over nn elements makes the overall time complexity of a heap sort O(n log(n))O(n \ log (n)). Learn how to implement a heap sort here.

Quick Sort

Like merge sort, quick sort is a divide-and-conquer algorithm that follows three essential steps:

  1. Select an element that is designated as the pivot from the array to be sorted.
  2. Move smaller elements to the left of the pivot and larger elements to the right of the pivot.
  3. Recursively apply steps 1 and 2 on the sub-arrays.

However, the choice of the pivot actually determines the performance of quicksort. If the first or the last element of the array is chosen as a pivot, then quicksort has a worst-case time complexity of O(n2)O(n^2). But, if a good pivot is chosen, the time complexity can be as good as O(n log(n))O(n \ log (n)) with performance exceeding that of merge sort. An implementation of quicksort in Java is given here.

RELATED TAGS

sorting
algorithms
nlogn
time complexity
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?