This is a homework question. I have been asked to identify what sort this code below implements.

sort(arr of length n, left, right):
  if (left > right): return 

  for i from 0 to n:
    if i >= right and arr[left] > arr[i]:
      left = i

  swap(arr, left, right)
  left = right
  right = right + 2
  if (right < n):
    sort(arr, left + 1, right - 1)
    sort(arr, right - 1, left)

    sort(arr, 0, 0)

After writing the code's trace on paper, I've come to think that it's a selection sort because from the original table [50, 15, 33, 27, 89, 12, 18] after passing one time through it we obtain [12, 15, 33, 27, 89, 50, 18]. We looked for the smallest element in the table and then put it first. this seems like the typical behavior of selection sort.

I want to confirm if I am right or wrong because I do not have access to the solution of the problem.

  • $\begingroup$ It does appear that the algorithm finds the smallest element at each iteration and swaps it forward. Though you may want to determine how right relates to all of this. Consider what it means if the if condition within the for loop never gets hit. Also, it may be worth noting that just before the recursive calls we have right = left + 2, thus the recursive calls would just be sort(arr, left + 1, left + 1) and sort(left + 1, left). What's the difference in these calls? (Hint: one of them does nothing) $\endgroup$
    – ryan
    Commented Apr 15, 2019 at 17:27
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. Perhaps a good next step for you would be to try a few more examples. $\endgroup$
    – D.W.
    Commented Apr 15, 2019 at 17:36
  • $\begingroup$ I also took some liberties with editing the question to cut it down to the core. Feel free to change them if this is not what you meant. Also make sure to address D.W.'s comment. $\endgroup$
    – ryan
    Commented Apr 15, 2019 at 17:38
  • $\begingroup$ Have you tried proving your suspicion? $\endgroup$ Commented Apr 15, 2019 at 18:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.