Bubble Sort is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they are in the wrong order. Bubble sort is a stable, in-place sort algorithm. How it works: In an unsorted array of n elements, start with the first two elements and sort them in ascending order. (Compare the element to check which one is greater). Compare the second and third element to check which one is greater, and sort them in ascending order. Compare the third and fourth element to check which one is greater, and sort them in ascending order. ... Repeat steps 1– n until no more swaps are required. Visualisation: Complexity Analysis: Time Complexity: O(n^2) Space Complexity: O(n^2) Bubble sort has a worst-case and average complexity of

O(

n2) , where n is the number of items being sorted. When the list is already sorted (best-case), the complexity of bubble sort is only O(n) . The space complexity for Bubble Sort is O(1) , because only single additional memory space is required (for temp swap element). Implementation: JS

// Normal
const bubbleSort = function(array) {
  let swaps;
  do {
    swaps = false;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        let temp = array[i + 1];
        array[i + 1] = array[i];
        array[i] = temp;
        swaps = true;
      }
  }
} while (swaps);
return array;
};// Recursively
const bubbleSort = function (array, pointer = array.length - 1) {
  // Base Case

  if (pointer === 0) {
    return array;
  }
for (let i = 0; i < pointer; i++) {
  if (array[i] > array[i + 1]) {
    let temp = array[i + 1];
    array[i + 1] = array[i];
    array[i] = temp;
  }
}
// Recursive call on smaller portion of the array
return bubbleSort(array, pointer - 1);
};
PY
def bubbleSort(arr):
n = len(arr)# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]

Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output. Sorting have direct applications in database algorithms, divide and conquer methods, data structure algorithms, and many more.

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements. So, by taking advantage of this property, we can pop off the max of the heap repeatedly and establish a sorted array. In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i , its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one). The HeapSort steps are: Create a max heap from the unsorted list Swap the max element, located at the root, with the last element Re- heapify or rebalance the array again to establish the max heap order. The new root is likely not in its correct place. Repeat Steps 2–3 until complete (when the list size is 1)

Visualisation: Complexity: Complexity Analysis: Time Complexity: O(n log n) Space Complexity: O(n log n) Best:

O(
n log n)
Average:
O(
n log n)
Worst:
O(
n log n)
Implementation:
JS
var a = [ 9, 10, 2, 1, 5, 4, 3, 6, 8, 7, 13 ];
function swap(a, i, j) {
  var tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}
function max_heapify(a, i, length) {
  while (true) {
    var left = i*2 + 1;

    var right = i*2 + 2;
    var largest = i;
    if (left < length && a[left] > a[largest]) {
      largest = left;
    }
  if (right < length && a[right] > a[largest]) {
    largest = right;
  }
if (i == largest) {
  break;
}
swap(a, i, largest);
i = largest;
}
}
function heapify(a, length) {
  for (var i = Math.floor(length/2); i >= 0; i--) {
    max_heapify(a, i, length);
  }
}
function heapsort(a) {
  heapify(a, a.length);
  for (var i = a.length - 1; i > 0; i--) {
    swap(a, i, 0);
    max_heapify(a, 0, i-1);
  }
}
heapsort(a);
PY
def heapsort(lst):
"""

Sorts list in-place with a heap. """

last_element = len(lst) - 1
lst = heapify(lst)
while last_element >= 0:
# swap the max element with the last element
# like popping off the max
swap(lst, 0, last_element)
# rebalance the remaining heap, from index 0 to last_element exclusive
balance(lst, 0, last_element)
last_element -= 1

return lst def heapify(lst): """ Turns list into a max heap in-place, in linear time. Begins process at 1 depth before leaves. """# initiliazes cur at halfway point based on length of list

if len(lst) % 2 == 0:
cur = len(lst) / 2 - 2
else:
cur = len(lst) / 2 - 1

# rebalance until reached beginning of list
while cur >= 0:
balance(lst, cur)
cur -= 1

return lst def swap(lst, i, last_element): """ Swaps two elments of a list - the current and last in this case. """ lst[i], lst[last_element] = lst[last_element], lst[i] def balance(lst, cur, last_element=None): """ Rebalances heap. Keyword arg for last_element allows for re-use in both heapify and heapsort. """ if last_element is None:

last_element = len(lst)
while cur < last_element:
left_child = 2*cur + 1
right_child = 2*cur + 2
# check to see if we're out of bounds for the children
# this is necessary for even length heaps
if left_child >= last_element:

return

if right_child >= last_element:
# since left child is in bounds, check for swap
if lst[cur] < lst[left_child]:
swap(lst, cur, left_child)

return

if we're in bounds for both children, find the max

max_child = find_max_child(lst, left_child, right_child)

check to see if swap needed

if lst[cur] < lst[max_child]:
swap(lst, cur, max_child)
cur = max_child

A stable sorting algorithm is the one that sorts the identical elements in their same order as they appear in the input, whilst unstable sorting may not satisfy the case.

Stable Sorting Algorithms: Insertion Sort Merge Sort Bubble Sort Tim Sort Counting Sort Unstable Sorting Algorithms: Heap Sort Selection sort Shell sort Quick Sort So stability matters if, and only if, the problem you're solving requires retention of that relative order. If you don't need stability, you can use a fast, memory-sipping algorithm from a library, like heapsort or quicksort, and forget about it. If you need stability, it's more complicated. Stable algorithms have higher big-O CPU and/or memory usage than unstable algorithms. So when you have a large data set, you have to pick between beating up the CPU or the memory.

Problem

They're both O(n log n) and yet most people use Quicksort instead of Mergesort. Why is that?

Solution

Quicksort has

O(
n2) worst-case runtime and
O(
n log n) average case runtime. However, it’s superior to

merge sort in many scenarios because many factors influence an algorithm’s runtime, and, when taking them all together, quicksort wins out. Quicksort in particular requires little additional space (it's in-place and MergeSort requires extra memory linear to number of elements to be sorted) and exhibits good cache locality (does half as many reads as the other algorithms), and this makes it faster than merge sort in many cases. In addition, it’s very easy to avoid quicksort’s worst-case run time of

O(
n2) almost entirely by using an appropriate choice of the pivot – such
as picking it at random (this is an excellent strategy).

The average case performance for quicksort is faster than mergesort. But this is only true if you are assuming constant time to access any piece of memory on demand. In RAM this assumption is generally not too

bad (it is not always true because of caches, but it is not too bad). However if your data structure is big enough

to live on disk, then quicksort gets killed by the fact that your average disk does something like 200 random seeks per second. if data has to be sorted on disk, you really, really want to use some variation of mergesort.

In internal sorting all the data to sort is stored in memory at all times while sorting is in progress. In external sorting data is stored outside memory (like on disk) and only loaded into memory in small chunks. External sorting is usually applied in cases when data can't fit into memory entirely. So in internal sorting you can do something like shell sort - just access whatever array elements you want at whatever moment you want. You can't do that in external sorting - the array is not entirely in memory, so you can't just randomly access any element in memory and accessing it randomly on disk is usually extremely slow. The external sorting algorithm has to deal with loading and unloading chunks of data in optimal manner. Divide and conquer algorithms like merge sort are commonly used for external sorting, because they break up the problem of sorting everything into a series of smaller sorts on chunks at a time. It doesn’t require random access to the the dataset and can be made to operate in chunks which fit in memory. In some cases the in- memory chunks maybe sorted using an in-memory (internal) sorting algorithm.

Only a few items: Insertion Sort Items are mostly sorted already: Insertion Sort Concerned about worst-case scenarios: Heap Sort Interested in a good average-case result: Quick Sort Items are drawn from a dense universe: Bucket Sort Desire to write as little code as possible: Insertion Sort

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements. So, by taking advantage of this property, we can pop off the max of the heap repeatedly and establish a sorted array. In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i , its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one). The HeapSort steps are:

Create a max heap from the unsorted list Swap the max element, located at the root, with the last element Re- heapify or rebalance the array again to establish the max heap order. The new root is likely not in its correct place. Repeat Steps 2–3 until complete (when the list size is 1) Visualisation: Complexity: Complexity Analysis: Time Complexity: O(n log n) Space Complexity: O(n log n) Best:

O(
n log n)
Average:
O(
n log n)
Worst:
O(
n log n)
Implementation:
JS
var a = [ 9, 10, 2, 1, 5, 4, 3, 6, 8, 7, 13 ];

function swap(a, i, j) {
  var tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}
function max_heapify(a, i, length) {
  while (true) {
    var left = i*2 + 1;
    var right = i*2 + 2;
    var largest = i;
    if (left < length && a[left] > a[largest]) {
      largest = left;
    }
  if (right < length && a[right] > a[largest]) {
    largest = right;
  }
if (i == largest) {
  break;
}
swap(a, i, largest);
i = largest;
}
}
function heapify(a, length) {
  for (var i = Math.floor(length/2); i >= 0; i--) {
    max_heapify(a, i, length);
  }
}
function heapsort(a) {
  heapify(a, a.length);
  for (var i = a.length - 1; i > 0; i--) {
    swap(a, i, 0);
    max_heapify(a, 0, i-1);
  }
}
heapsort(a);
PY
def heapsort(lst):
"""

Sorts list in-place with a heap. """

last_element = len(lst) - 1
lst = heapify(lst)
while last_element >= 0:
# swap the max element with the last element
# like popping off the max
swap(lst, 0, last_element)
# rebalance the remaining heap, from index 0 to last_element exclusive
balance(lst, 0, last_element)
last_element -= 1

return lst def heapify(lst): """

Turns list into a max heap in-place, in linear time. Begins process at 1 depth before leaves. """# initiliazes cur at halfway point based on length of list

if len(lst) % 2 == 0:
cur = len(lst) / 2 - 2
else:
cur = len(lst) / 2 - 1# rebalance until reached beginning of list
while cur >= 0:
balance(lst, cur)
cur -= 1

return lst def swap(lst, i, last_element): """ Swaps two elments of a list - the current and last in this case. """ lst[i], lst[last_element] = lst[last_element], lst[i] def balance(lst, cur, last_element=None): """ Rebalances heap. Keyword arg for last_element allows for re-use in both heapify and heapsort. """ if last_element is None:

last_element = len(lst)
while cur < last_element:
left_child = 2*cur + 1
right_child = 2*cur + 2
# check to see if we're out of bounds for the children
# this is necessary for even length heaps
if left_child >= last_element:

return

if right_child >= last_element:
# since left child is in bounds, check for swap
if lst[cur] < lst[left_child]:
swap(lst, cur, left_child)

return

if we're in bounds for both children, find the max

max_child = find_max_child(lst, left_child, right_child)

check to see if swap needed

if lst[cur] < lst[max_child]:
swap(lst, cur, max_child)
cur = max_child

First, a definition, since it's pretty important: A stable sort is one that's guaranteed not to reorder elements with identical keys. Recommendations when to use different sorting algos:

Quick sort: When you don't need a stable sort and average case performance matters more than worst case performance. A quick sort is O(N log N) on average, O(N^2) in the worst case. A good implementation uses O(log N) auxiliary storage in the form of stack space for recursion. In 99% of the cases, you'll be fine with the library sorts, which are usually based on quicksort. Merge sort: When you need a stable, O(N log N) sort, this is about your only option. The only downsides to it are that it uses O(N) auxiliary space and has a slightly larger constant than a quick sort. There are some in-place merge sorts, but AFAIK they are all either not stable or worse than O(N log N) . Even the O(N log N) in place sorts have so much larger a constant than the plain old merge sort that they're more theoretical curiosities than useful algorithms. Heap sort: When you don't need a stable sort and you care more about worst case performance than average case performance. It's guaranteed to be O(N log N) , and uses O(1) auxiliary space, meaning that you won't unexpectedly run out of heap or stack space on very large inputs. Introsort: This is a quick sort that switches to a heap sort after a certain recursion depth to get around quick sort's O(N^2) worst case. It's almost always better than a plain old quick sort, since you get the average case of a quick sort, with guaranteed O(N log N) performance. Probably the only reason to use a heap sort instead of this is in severely memory constrained systems where O(log N) stack space is practically significant. Insertion sort: When N is guaranteed to be small, including as the base case of a quick sort or merge sort. While this is O(N^2) , it has a very small constant and is a stable sort. Bubble sort, selection sort: When you're doing something quick and dirty and for some reason you can't just use the standard library's sorting algorithm. The only advantage these have over insertion sort is being slightly easier to implement. Non-comparison sorts: Under some fairly limited conditions it's possible to break the O(N log N) barrier and sort in O(N) . Here are some cases where that's worth a try: Counting sort: When you are sorting integers with a limited range. Radix sort: When log(N) is significantly larger than K , where K is the number of radix digits. Bucket sort: When you can guarantee that your input is approximately uniformly distributed.

Merge sort is a divide-and-conquer, comparison-based sorting algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Can be used as external sorting (when the data to be sorted is too large to fit into memory). There are two methods for implementing a Merge Sort algorithm: The Top-Down (recursive) approach. Given an array of size N, the algorithm recursively breaks the array in half and then merges the results together. The Bottom-Up (iterative) approach. Rather than breaking the overall array into distinct pieces, bottum-up mergesort loops over the array using intervals of varying sizes. Each interval is sorted and merged together; subsequent loops over the array have larger intervals, effectively merging our previously sorted (smaller) intervals together. Complexity Analysis: Time Complexity: O(n log n) Space Complexity: O(n log n)

The list of size n is divided into a max of log n parts (the height of the conquer step tree is log n + 1 for a given n ), and the merging of all sublists into a single list takes O(n) time, the worst case run time of this algorithm is O(n log n) . Space complexity is always Ω(n) as you have to store the elements somewhere. Additional space complexity can be O(n) in an implementation using arrays and O(1) in linked list implementations. In practice implementations using lists need additional space for list pointers, so unless you already have the list in memory it shouldn't matter. Implementation: JS

The Top-Down (recursive) approach
function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
let midpoint = Math.floor(arr.length / 2);
let leftHalf = arr.slice(0, midpoint);
//slice an array of left-half items
let rightHalf = arr.slice(midpoint);
//slice an array of right-half items
//recurse into each half until arrays are 1 item each
//then merge() the sorted arrays on each layer of the stack
return merge(mergeSort(leftHalf), mergeSort(rightHalf));
}//first time this merge() gets called, the arr's are both 1 element long
//on each layer of the stack the arrs will be doubled and always be sorted
function merge(arrA, arrB) {
  let a = 0;
  let b = 0;
  let result = [];
  while (a < arrA.length && b < arrB.length) {
    if (arrA[a] < arrB[b]) {
      result.push(arrA[a]);
      a++;
    } else {
      result.push(arrB[b]);
      b++;
    }
}

//using slice to concat remaining items left in either arrA or arrB
return result.concat(arrA.slice(a)).concat(arrB.slice(b));
}//usage:
mergeSort([4,2,8,3,6,9,1]);
//=> [1,2,3,4,6,8,9]
The Bottom-Up (iterative) approach
function mergeSort(arr) {
  var sorted = arr.slice(),
  n = sorted.length,
  buffer = new Array(n);
  for (var size = 1; size < n; size *= 2) {
    for (var leftStart = 0; leftStart < n; leftStart += 2 * size) {
      var left = leftStart,
      right = Math.min(left + size, n),
      leftLimit = right,
      rightLimit = Math.min(right + size, n),
      i = left;
      while (left < leftLimit && right < rightLimit) {
        if (sorted[left] <= sorted[right]) {
          buffer[i++] = sorted[left++];
        } else {
          buffer[i++] = sorted[right++];
        }
    }
  while (left < leftLimit) {
    buffer[i++] = sorted[left++];
  }
while (right < rightLimit) {
  buffer[i++] = sorted[right++];
}
}
var temp = sorted,
sorted = buffer,
buffer = temp;
}
return sorted;
}
PY
The Top-Down (recursive) approach
def merge_lists(left_sublist,right_sublist):
i,j = 0,0
result = []

#iterate through both left and right sublist

while i<len(left_sublist) and j<len(right_sublist):

#if left value is lower than right then append it to the result

if left_sublist[i] <= right_sublist[j]:
result.append(left_sublist[i])
i += 1
else:

#if right value is lower than left then append it to the result

result.append(right_sublist[j])
j += 1

#concatenate the rest of the left and right sublists

result += left_sublist[i:]
result += right_sublist[j:]

#return the result return result def merge_sort(input_list):

#if list contains only 1 element return it

if len(input_list) <= 1:

return input_list else: #split the lists into two sublists and recursively split sublists

midpoint = int(len(input_list)/2)
left_sublist = merge_sort(input_list[:midpoint])
right_sublist = merge_sort(input_list[midpoint:])

#return the merged list using the merge_list function above return merge_lists(left_sublist,right_sublist) #test run

number_list = [3,1,5,3,2,5,8,2,9,6,12,53,75,22,83,123,12123]
print merge_sort(number_list)
The Bottom-Up (iterative) approach
def merge_sort_iterative(data):
for j in range(1, len(data)):
j *= 2
for i in range(0,len(data),j):
data_1 = data[i:i+(j/2)]
data_2 = data[i+(j/2):j-i]
l = m = 0
while l < len(data_1) and m < len(data_2):
if data_1[l] < data_2[m]:
m += 1
elif data_1[l] > data_2[m]:
data_1[l], data_2[m] = data_2[m], data_1[l]
l += 1
data[i:i+(j/2)], data[i+(j/2):j-i] = data_1, data_2

return data

Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. Note that recursive approach requires Θ(log n) extra space, since you'll have Θ(log n) calls on the stack when you're all the way down to merge-sorting a singleton-list. To reduce it to O(1) extra space, you'll need to change from a recursive "top-down" approach to an iterative "bottom-up" approach. Implementation: Java

// The main function
public static Node merge_sort(Node head)
{
  if(head == null || head.next == null)
  return head;
  Node middle = getMiddle(head);
  //get the middle of the list
  Node left_head = head;
  Node right_head = middle.next;

  middle.next = null;
  //split the list into two halfs
  return merge(merge_sort(left_head), merge_sort(right_head));
  //recurse on that
}// Merge subroutine to merge two sorted lists
public static Node merge(Node a, Node b)
{
  Node dummyHead = new Node();
  for(Node current = dummyHead; a != null && b != null; current = current.next;)
  {
    if(a.data <= b.data)
    {
      current.next = a;
      a = a.next;
    }
  else
  {
    current.next = b;
    b = b.next;
  }
}
current.next = (a == null) ? b : a;
return dummyHead.next;
}// Utility function to get the middle of the linked list
public static Node getMiddle(Node head) {
  if (head == null)
  return head;
  Node slow = head, fast = head;
  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
return slow;
}

A stack performs push and pop operations. So, the push and pop operations are carried out between theinput_stack and the auxilary_stack in such a way that the auxiliary stack contains the sorted input stack. Solution Steps:

1. Create a temporary stack say aux_stack.
2. Repeat until the input_stack is not empty
3. Pop an element from input_stack call it temp_value.
4. While aux_stack is not empty and top of the aux_stack < temp_value, pop data from aux_stack and push it to the input_stack
5. Push temp_value to the aux_stack
6. return the aux_stack. Implementation:

Java Stack sort_stack(Stack input_stack) { Stack aux_stack

while(!input_stack.empty())
{
  int temp_value = input_stack.top()
  input_stack.pop()
  while(!aux_stack.empty() and aux_stack.top() > temp) {
    input_stack.push(aux_stack.top())
    aux_stack.pop()
  }
aux_stack.push(temp_value)
}

return aux_stack

}
PY
# Sort using insertion sort with stacks O(n^2)
def sort_stack(l):
res_stack = deque()# We keep res_stack always sorted
while len(l) > 0:
current = l.pop()
while True:
if len(res_stack) == 0:
res_stack.append(current)
break
elem = res_stack.pop()
if elem <= current:
res_stack.append(elem)
res_stack.append(current)
break
else:
l.append(elem)

return res_stack

A stable sorting algorithm is the one that sorts the identical elements in their same order as they appear in the input, whilst unstable sorting may not satisfy the case.

Stable Sorting Algorithms: Insertion Sort Merge Sort Bubble Sort Tim Sort Counting Sort Unstable Sorting Algorithms: Heap Sort Selection sort Shell sort Quick Sort So stability matters if, and only if, the problem you're solving requires retention of that relative order. If you don't need stability, you can use a fast, memory-sipping algorithm from a library, like heapsort or quicksort, and forget about it. If you need stability, it's more complicated. Stable algorithms have higher big-O CPU and/or memory usage than unstable algorithms. So when you have a large data set, you have to pick between beating up the CPU or the memory.

The brute force solution will be to sort the array in O(n log n) time complexity and take the last 100 numbers but you can do better. You can keep a priority queue (implemented as a heap) of the 100 biggest numbers, iterate through the billion numbers, whenever you encounter a number greater than the smallest number in the queue (the head of the queue), remove the head of the queue and add the new number to the queue. In general, if you need the largest K numbers from a set of N numbers, the complexity is O(N log K) rather than O(N log N) , this can be very significant when K is very small comparing to N . You can also apply problem solving process. Ask interviewer the range or meaning of these numbers to make the problem clear. If, for example, these numbers stands for people's age of within a country (e.g. China), then it's a much easier problem. With a reasonable assumption that nobody alive is older than 200, you can use an int array of size 200 (maybe 201) to count the number of people with the same age in just one iteration. Here the index means the age. After this it's a piece of cake to find 100 largest number. By the way this also is called counting sort. Counting sort takes O(n + k) time and O(n + k) space, where n is the number of items we're sorting and k is the number of possible values.

Radix sort is a sorting technique that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order. Radix sort uses counting sort as a subroutine to sort an array of numbers. Because integers can be used to represent strings (by hashing the strings to integers), radix sort works on data types other than just integers. Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For example, a binary system (using numbers 0 and 1) has a radix of 2 and a decimal system (using numbers 0 to 9) has a radix of 10. Radix sorts can be implemented to start at either the most significant digit (MSD) or least significant digit (LSD). For example, with 1234 , one could start with 1 (MSD) or 4 (LSD). Assume the input array is [123, 2, 999, 609, 111] :

1. Based on the algorithm, we will sort the input array according to the one's digit (least significant digit, LSD):

[0]:

[1]: 111
[2]: 002
[3]: 123
[4]:
[5]:
[6]:
[7]:
[8]:
[9]: 999, 609
// Note that we placed 999 before 609 because it appeared first.

2. Now, we'll sort according to the ten's digit:

[0]: 609, 002
[1]: 111
[2]: 123
[3]:
[4]:
[5]:
[6]:
[7]:
[8]:
[9]: 999
3. Finally , we sort according to the hundred's digit (most significant digit):
[0]: 002
[1]: 111, 123
[2]:
[3]:
[4]:
[5]:
[6]: 609
[7]:
[8]:
[9]: 999
Complexity Analysis:
Time Complexity: O(n) Space Complexity: O(n)
Radix sort will operate on n d-digit numbers where each digit can be one of at most b different values (since b

is the base (or radix) being used). For example, in base 10, a digit can be 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 or 9 . Radix sort uses counting sort on each digit. Each pass over n d -digit numbers will take O(n + b) time, and there are d passes total. Therefore, the total running time of radix sort is O(d(n+b)) . When d is a constant and b isn't much larger than n (in other words, b=O(n) ), then radix sort takes linear time. The space complexity comes from counting sort, which requires O(n+b) space to hold the counts, indices, and output lists. Implementation: JS

/* Radix Sort implementation in JavaScript */
function radixSort(arr) {
  var maxDigit = getMaxDigitLen(arr);//Looping for every digit index from leftmost digits to rightmost digits
  for (var i = 1; i <= maxDigit; i++) {
    // rebuild the digit buckets according to this digit
    var digitBuckets = [];
    for (var j = 0; j < arr.length; j++) {
      var digit = getDigit(arr[j], i);
      //get the i-th digit of the j-th element of the array
      digitBuckets[digit] = digitBuckets[digit] || [];
      //If empty initialize with empty array
      digitBuckets[digit].push(arr[j]);
      //Add the number in it's respective digits bucket
    }
  // rebuild the array according to this digit
  var index = 0;
  for (var k = 0; k < digitBuckets.length; k++) {
    if (digitBuckets[k] && digitBuckets[k].length > 0) {
      for (j = 0; j < digitBuckets[k].length; j++) {
        arr[index++] = digitBuckets[k][j];
      }
  }
}
}
return arr;
}// helper function to get the last n-th(position) digit of a number
var getDigit = function(num, position) {
  var num_length = num.toString().length;
  if (num_length < position)
  return 0;
  var radixPosition = Math.pow(10, position - 1);
  //number with the positions-th power of 10
  /*

Logic: To find the 2nd digit of the number 123 we can divide it by 10, which is 12 and the using the modulus operator(%) we can find 12 % 10 = 2

*/
var digit = (Math.floor(num / radixPosition)) % 10;
return digit;
};// helper function get the length of digits of the max value in this array
var getMaxDigitLen = function(arr) {
  var maxVal = Math.max.apply(Math, arr);
  //Finding max value from the array
  return Math.ceil(Math.log10(maxVal));
};
PY
import math
def counting_sort(A, digit, radix):

#"A" is a list to be sorted, radix is the base of the number system, digit is the digit #we want to sort by #create a list B which will be the sorted list

B = [0]*len(A)
C = [0]*int(radix)

#counts the number of occurences of each digit in A

for i in range(0, len(A)):
digit_of_Ai = (A[i]/radix**digit)%radix

C[digit_of_Ai] = C[digit_of_Ai] +1
#now C[i] is the value of the number of elements in A equal to i

#this FOR loop changes C to show the cumulative # of digits up to that index of C

for j in range(1,radix):
C[j] = C[j] + C[j-1]
#here C is modifed to have the number of elements <= i
for m in range(len(A)-1, -1, -1):
#to count down (go through A backwards)
digit_of_Ai = (A[m]/radix**digit)%radix
C[digit_of_Ai] = C[digit_of_Ai] -1
B[C[digit_of_Ai]] = A[m]

return B def radix_sort(A, radix): #radix is the base of the number system #k is the largest number in the list

k = max(A)

#output is the result list we will build output = A #compute the number of digits needed to represent k

digits = int(math.floor(math.log(k, radix)+1))
for i in range(digits):
output = counting_sort(output,i,radix)

return output

Quicksort depends on being able to index (or random access) into an array or similar structure. When that's possible, it's hard to beat Quicksort. You can't index directly into a linked list very quickly. That is, if myList is a linked list, then myList[x] , were it possible to write such syntax, would involve starting at the head of the list and following the first x links. That would have to be done twice for every comparison that Quicksort makes, and that would get expensive real quick. Same thing on disk - Quicksort would have to seek and read every item it wants to compare. Merge sort is faster in these situations because it reads the items sequentially, typically making log(n) passes over the data. There is much less I/O involved, and much less time spent following links in a linked list. Quicksort is fast when the data fits into memory and can be addressed directly. Mergesort is faster when data won't fit into memory or when it's expensive to get to an item.

Mergesort advantages over Quicksort are: Mergesort is worst-case

O(
n log n) , Quicksort is average case
O(
n log n) , but has a worst case of
O(
n2)

Mergesort is stable by design, equal elements keep their original order Mergesort is well suited to be implemented parallel (multithreading) Mergesort uses (about 30%) less comparisons than QuickSort. This is an often overlooked advantage, because a comparison can be quite expensive (e.g. when comparing several fields of database rows) Mergesort is a superior algorithm for sorting linked lists, since it makes fewer total comparisons Linked lists can be merged with only O(1) space overhead instead of O(n) space overhead Quicksort usually is better than mergesort for two reasons: Quicksort has better locality of reference than mergesort, which means that the accesses performed in quicksort are usually faster than the corresponding accesses in mergesort. Quicksort uses worst-case O(log n) memory (if implemented correctly), while mergesort requires O(n) memory due to the overhead of merging. Scenarios when quicksort is worse than mergesort: Array is already sorted All elements in the array are the same Array is sorted in reverse order

Quicksort depends on being able to index (or random access) into an array or similar structure. When that's possible, it's hard to beat Quicksort. You can't index directly into a linked list very quickly. That is, if myList is a linked list, then myList[x] , were it possible to write such syntax, would involve starting at the head of the list and following the first x links. That would have to be done twice for every comparison that Quicksort makes, and that would get expensive real quick. Same thing on disk - Quicksort would have to seek and read every item it wants to compare. Merge sort is faster in these situations because it reads the items sequentially, typically making log(n) passes over the data. There is much less I/O involved, and much less time spent following links in a linked list. Quicksort is fast when the data fits into memory and can be addressed directly. Mergesort is faster when data won't fit into memory or when it's expensive to get to an item.

Quick Sort is a divide and conquer, comparison, in-place algorithm. Efficient implementations of Quicksort are not a stable sort. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. Quicksort determines something called a pivot, which is a somewhat arbitrary element in the collection. Using the pivot point, quicksort partitions (or divides) the larger unsorted collection into two, smaller lists. It moves all the elements smaller than the pivot to the left (before) the pivot element, and moves all the elements larger than the pivot to the right (after) the pivot element. Even though the list isn’t completely sorted yet, we know that the items are in the correct order in relation to the pivot. This means that we never have to compare elements on the left side of the partition to elements on the right side of the partition. We already know they are in their correct spots in relation to the pivot. The sub-lists are then sorted recursively. Ideally, partitioning would use the median of the given values (in the array), but the median can only be found by scanning the whole array and this would slow the algorithm down. In that case the two partitions would be of equal size; In the simplest versions of quick sort an arbitrary element, typically the

last (rightmost) element is
used as an estimate (guess) of the median.
Complexity Analysis:
Time Complexity: O(n log n) Space Complexity: O(n log n)

Overall time complexity of Quick Sort is

O(
n log n) . In the worst case, it makes
O(
n2) comparisons (all elements
are same or array is already sorted).
The partition step used in quicksort ideally is an in-place operation (without creating any additional arrays). But
since quicksort calls itself on the order of log(n) times (in the average case), worst case number of calls isO(
n) , at each recursive call a new stack frame of constant size must be allocated. Hence the
O(
log n) space
complexity.
Implementation:
JS
With additional memory (naive):

function quickSort (arr) {
  if(arr.length <= 1) return arr;// find middle point of array (effectively random pivot)
  var swapPosition = Math.floor((arr.length -1) / 2);
  var pivot = arr.splice(swapPosition, 1);
  var left = [];
  var right = [];
  for(var i = 0; i < arr.length; i++) {
    if(arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i])
    }
}
return quickSort(left).concat(pivot, quickSort(right));
}

In-place:

var quickSort = function(array, left, right) {
  var leftIndex = partition(array, left, right);
  if (left < leftIndex - 1) {
    quickSort(array, left, leftIndex - 1);
  }
if (right > leftIndex) {
  quickSort(array, leftIndex, right);
}
return array;
}
var swap = function(array, left, right) {
  var temp;
  temp = array[leftIndex];
  array[leftIndex] = array[rightIndex];
  array[rightIndex] = temp;
}
var partition = function(array, left, right) {
  var pivotIndex = Math.floor((left + right) / 2);
  var pivot = array[pivotIndex];
  leftIndex = left;
  rightIndex = right;
  while (leftIndex <= rightIndex) {
    while (array[leftIndex] < pivot) {
      leftIndex++;
    }
  while (array[rightIndex] > pivot) {
    rightIndex--;
  }
if (leftIndex <= rightIndex) {
  swap(array, left, right);
  leftIndex++;
  rightIndex--;
}
}
return leftIndex;
}

PY
With additional memory (naive):
def quick_sort(collection):
length = len(collection)
if length <= 1:

return collection else:

Use the last element as the first pivot

pivot = collection.pop()
# Put elements greater than pivot in greater list
# Put elements lesser than pivot in lesser list
greater, lesser = [], []
for element in collection:
if element > pivot:
greater.append(element)
else:
lesser.append(element)
return quick_sort(lesser) + [pivot] + quick_sort(greater)
Quick sort without additional memory (in place):
def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]

return pivot def quicksort(array, begin=0, end=None): if end is None:

end = len(array) - 1
def _quicksort(array, begin, end):
if begin >= end:

return

pivot = partition(array, begin, end)
_quicksort(array, begin, pivot-1)
_quicksort(array, pivot+1, end)
return _quicksort(array, begin, end)

Advantages: Simple to understand Ability to detect that the list is sorted efficiently is built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n) . Disadvantages: It is very slow and runs in

O(
n2) time in worst as well as average case. Because of that Bubble sort does not
deal well with a large set of data. For example Bubble sort is three times slower than Quicksort even for n =

100

The add() method below walks down the list until it finds the appropriate position. Then, it splices in the new node and updates the start , prev , and curr pointers where applicable. Note that the reverse operation, namely removing elements, doesn't need to change, because you are simply throwing things away which would not change any order in the list. Implementation: Java

public void add(T x) {
  Node newNode = new Node();
  newNode.info = x;// case: start is null; just assign start to the new node and return
  if (start == null) {
    start = newNode;
    curr = start;
    // prev is null, hence not formally assigned here
    return;
  }// case: new node to be inserted comes before the current start;
//

in this case, point the new node to start, update pointers, and return

if (x.compareTo(start.info) < 0) {
  newNode.link = start;
  start = newNode;
  curr = start;
  // again we leave prev undefined, as it is null
  return;
}// otherwise walk down the list until reaching either the end of the list
// or the first position whose element is greater than the node to be
// inserted; then insert the node and update the pointers
prev = start;
curr = start;
while (curr != null && x.compareTo(curr.info) >= 0) {
  prev = curr;
  curr = curr.link;
}// splice in the new node and update the curr pointer (prev already correct)
newNode.link = prev.link;
prev.link = newNode;
curr = newNode;
}

Insertion Sort is an in-place, stable, comparison-based sorting algorithm. The idea is to maintain a sub-list which is always sorted. An element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort. Steps on how it works: If it is the first element, it is already sorted. Pick the next element. Compare with all the elements in sorted sub-list. Shift all the the elements in sorted sub-list that is greater than the value to be sorted. Insert the value. Repeat until list is sorted. Visualisation: Complexity Analysis: Time Complexity: O(n^2) Space Complexity: O(n^2) Insertion sort runs in

O(
n2) in its worst and average cases. It runs in O(n) time in its best case.

Insertion sort performs two operations: it scans through the list, comparing each pair of elements, and it swaps elements if they are out of order. Each operation contributes to the running time of the algorithm. If the input array is already in sorted order, insertion sort compares O(n) elements and performs no swaps. Therefore, in the best case, insertion sort runs in O(n) time. Space complexity is O(1) because an extra variable key is used (as a temp variable for insertion). Implementation: JS

var insertionSort = function(a) {
  // Iterate through our array
  for (var i = 1, value; i < a.length; i++) {
    // Our array is split into two parts: values preceeding i are sorted, while others are unsorted
    // Store the unsorted value at i
    value = a[i];
    // Interate backwards through the unsorted values until we find the correct location for our
    `next` value
    for (var j = i; a[j - 1] > value; j--) {
      // Shift the value to the right

      a[j] = a[j - 1];
    }
  // Once we've created an open "slot" in the correct location for our value, insert it
  a[j] = value;
}
// Return the sorted array
return a;
};
Java
import java.util.Arrays;
class InsertionSort {
  void insertionSort(int array[]) {
    int size = array.length;
    for (int step = 1; step < size; step++) {
      int key = array[step];
      int j = step - 1;
      // Compare key with each element on the left of it until an element smaller than
      // it is found.
      // For descending order, change key<array[j] to key>array[j].
      while (j >= 0 && key < array[j]) {
        array[j + 1] = array[j];
        --j;
      }
    // Place key at after the element just smaller than it.
    array[j + 1] = key;
  }
}// Driver code
public static void main(String args[]) {
  int[] data = { 9, 5, 1, 4, 3 };
  InsertionSort is = new InsertionSort();
  is.insertionSort(data);
  System.out.println("Sorted Array in Ascending Order: ");
  System.out.println(Arrays.toString(data));
}
}
PY
def insertionSort(array):
for step in range(1, len(array)):
key = array[step]
j = step - 1
# Compare key with each element on the left of it until an element smaller than it is found
# For descending order, change key<array[j] to key>array[j].
while j >= 0 and key < array[j]:
array[j + 1] = array[j]
j = j - 1
# Place key at after the element just smaller than it.
array[j + 1] = key
data = [9, 5, 1, 4, 3]
insertionSort(data)
print('Sorted Array in Ascending Order:')
print(data)

In Bubble sort, you know that after k passes, the largest k elements are sorted at the k last entries of the array, so the conventional Bubble sort uses:

public static void bubblesort(int[] a) {
  for (int i = 1; i < a.length; i++) {
    boolean is_sorted = true;
    for (int j = 0; j < a.length - i; j++) {
      // skip the already sorted largest elements, compare to
      a.length - 1
      if (a[j] > a[j+1]) {
        int temp = a[j];
        a[j] = a[j+1];
        a[j+1] = temp;
        is_sorted = false;
      }
  }
if(is_sorted) return;
}
}

Now, that would still do a lot of unnecessary iterations when the array has a long sorted tail of largest elements. If you remember where you made your last swap, you know that after that index, there are the largest elements in order, so:

public static void bubblesort(int[] a) {
  int lastSwap = a.length - 1;
  for (int i = 1; i< a.length; i++) {
    boolean is_sorted = true;
    int currentSwap = -1;
    for (int j = 0; j < lastSwap; j++) {
      // compare to a.length - i
      if (a[j] > a[j+1]) {
        int temp = a[j];
        a[j] = a[j+1];
        a[j+1] = temp;
        is_sorted = false;
        currentSwap = j;
      }
  }
if (is_sorted) return;
lastSwap = currentSwap;
}
}

This allows to skip over many elements, resulting in about a worst case 50% improvement in comparison count (though no improvement in swap counts), and adds very little complexity.

The idea of an in-place algorithm isn't unique to sorting, but sorting is probably the most important case, or at least the most well-known. The idea is about space efficiency - using the minimum amount of RAM, hard disk or other storage that you can get away with. The idea is to produce an output in the same memory space that contains the input by successively transforming that data until the output is produced. This avoids the need to use twice the storage - one area for the input and an equal-sized area for the output. Quicksort is one example of In-Place Sorting.

Sorting algorithms can be categorised based on the following parameters:

1. Based on Number of Swaps or Inversion. This is the number of times the algorithm swaps elements to sort the input. Selection Sort requires the minimum number of swaps.
2. Based on Number of Comparisons. This is the number of times the algorithm compares elements to sort the input. Using Big-O notation, the sorting algorithm examples listed above require at least

O(
n log n)

comparisons in the best case and

O(

n2) comparisons in the worst case for most of the outputs. 3. Based on Recursion or Non-Recursion. Some sorting algorithms, such as Quick Sort , use recursive techniques to sort the input. Other sorting algorithms, such as Selection Sort or Insertion Sort , use non- recursive techniques. Finally, some sorting algorithm, such as Merge Sort , make use of both recursive as well as non-recursive techniques to sort the input. 4. Based on Stability. Sorting algorithms are said to be stable if the algorithm maintains the relative order of elements with equal keys. In other words, two equivalent elements remain in the same order in the sorted output as they were in the input. Insertion sort , Merge Sort , and Bubble Sort are stable Heap Sort and Quick Sort are not stable 5. Based on Extra Space Requirement. Sorting algorithms are said to be in place if they require a constant

O(
1) extra space for sorting.

Insertion sort and Quick-sort are in place sort as we move the elements about the pivot and do not actually use a separate array which is NOT the case in merge sort where the size of the input must be allocated beforehand to store the output during the sort. Merge Sort is an example of out place sort as it require extra memory space for it’s operations.

The Ideal Sorting Algorithm would have the following properties: Stable: Equal keys aren’t reordered. Operates in place: requiring O(1) extra space. Worst-case O(n log n) key comparisons. Worst-case O(n) swaps. Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys. There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.