CODEWITHSUNDEEP
csorting
JackDremo
JackDremo

Reputation: 13

STB Library Quicksort Implementation

I am reading the source code for Sean Barrett's "stb.h" library, and I have a question about the implementation of Quick Sort.

https://pastebin.com/gpfXTuL8

So, I am particularly confused about the following excerpt:

/* recurse on smaller side, iterate on larger */                        \
  if (j < (n-i)) {                                                        \
     STB_(FUNCNAME,_quicksort)(p,j);                                       \
     p = p+i;                                                             \
     n = n-i;                                                             \
  } else {                                                                \
     STB_(FUNCNAME,_quicksort)(p+i, n-i);                                  \
     n = j;                                                               \
  }

i don't get why the library chooses to recurse on the smaller side and iterate on the larger one; in the end aren't they both just going to execute the function from the beginning with updated p and n? i don't speak English too well, so if you need further clarification, I would be glad to provide it.

Upvotes: 1

Views: 106

Answers (1)

rcgldr
rcgldr

Reputation: 28931

Iterating on the larger part and only using recursion for the smaller part reduces used stack space to O(log(n)), otherwise worst case stack space is O(n). The worst case time complexity remains at O(n^2). Time complexity can be reduced by checking for excessive number of partition splits and switching to heap sort if the splits become excessive, such as intro sort.

Upvotes: 1

Related Questions