Recursive vs non-recursive sorting algorithms

Question

Can someone explain in English how non-recursive and recursive implementations of sorting algorithms differs from each other?

score 6 · Answer 1 · edited May 23 '17 at 12:09

6

How they differ, in what sense? Bear in mind: any recursive algorithm can be implemented as an iterative algorithm, and vice versa (take a look at this post). Iteration or recursion - it's just an implementation detail; although it can have a major impact in performance depending on the choice, the algorithm will be the same nevertheless.

edited May 23 '17 at 12:09

Community

1
1

answered Aug 19 '12 at 23:01

Óscar López

232,561
37
312
386

score 2 · Accepted Answer · answered Aug 19 '12 at 22:56

2

Recursive sorting algorithms work by splitting the input into two or more smaller inputs and then sorting those, then combining the results. Merge sort and quick sort are examples of recursive sorting algorithms.

A non-recursive technique is anything that doesn't use recursion. Insertion sort is a simple example of a non-recursive sorting algorithm.

answered Aug 19 '12 at 22:56

Mark Byers

811,555
193
1,581
1,452

2

This is mostly true, so I won't downvote it, but any recursive algorithm, sorting or not, can be made into a non-recursive (aka iterative) algorithm. – lordcheeto Oct 18 '12 at 17:09
Insertion Sort can be implemented recursively as well. Here is one example: http://www.geeksforgeeks.org/recursive-insertion-sort/ – p_sutherland Dec 05 '17 at 04:39

score 0 · Answer 3 · answered Aug 19 '12 at 22:56

A recursive sorting algorithm calls on itself to sort a smaller part of the array, then combining the partially sorted results. Quick-sort is an example.

A non-recursive algorithm does the sorting all at once, without calling itself. Bubble-sort is an example of a non-recursive algorithm.

Recursive vs non-recursive sorting algorithms

3 Answers3