CODEWITHSUNDEEP
sortingrecursionlogic
Alex Coronas
Alex Coronas

Reputation: 446

Sort List Recursively

At school we learned about recursion, and it's a fairly easy concept to grasp on. But it's fairly confusing to understand why it should be used on certain situations. It makes a lot of sense to browse directories recursively, or calculate factorials and stuff like that, but, my teacher mentioned that recursion is good for sorting lists.

How's that? Can anybody explain me why (and how, if possible) would you do that?

Thanks in advance.

Upvotes: 0

Views: 353

Answers (3)

rcgldr
rcgldr

Reputation: 28921

Assuming that "list" is the equivalent of an array as opposed to a linked list, then some sort algorithms like quicksort are recursive. On the other hand, iterative bottom up merge sort is generally a bit faster than recursive top down merge sort, and most actual libraries with a variation of merge sort use a bottom up iterative variation of merge sort.

Using recursion to calculate factorial is slow compared to iteration, since values are pushed onto the stack as opposed to register based calculations assuming an optimizing compiler.

One of the worst case scenarios for recursion is calculating a Fibonacci number using recursion, with a time complexity of O(2^n), versus iteration with time complexity of O(n).

In some cases, a type of recursion called "tail recursion" may be converted into a loop by a compiler.

Upvotes: 0

Yuriy F
Yuriy F

Reputation: 361

One simple reason is that when sorting a list, one doesn't need to know the size or number of iterations the function "recurs" or executes. The algorithm will run until a final condition is met (for example, the largest number is at the last index when sorting numbers in an ascending order).

Upvotes: 0

John T
John T

Reputation: 335

An excellent example of recursion for "sorting a list" is the quicksort algorithm which has order of magnitude, on average O(n log n) and worst case: O(n²)

Here is a nice example from https://www.geeksforgeeks.org/quick-sort/

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Upvotes: 1

Related Questions