> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/moderate/sub-sort.md).

# Sub Sort

**16.16 Sub Sort:** Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n - m (that is, find the smallest such sequence).

```
EXAMPLE
Input: 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19
Output: (3, 9)
```

* Iterate from the beginning, and make sure every element after it is large than it. When it is not, return this index. Now iterating from the end, and make sur every element before it is smaller than it. When it is not, return that index.

```cpp
pair<int, int> sub_sort(vector<int> &nums) {
    // assume to be sorted, and then change values if needed
    pair<int, int> n_m = { make_pair(0, nums.size() - 1) };
    if (nums.size() < 2) {
        cout << "Is sorted" << endl;
        return n_m;
    }

    bool notstop = true;
    for (int i = 0; i < nums.size() && notstop; i++) {
        for (int j = i+1; j < nums.size() && notstop; j++) {
            //cout << nums.at(i) << "<" << nums.at(j) << endl;
            if (nums.at(i) >= nums.at(j)) {
                n_m.first = i;
                notstop = false;
            }
        }
    }

    notstop = true;
    for (int i = nums.size() - 1; i >=0 && notstop; i--) {
        for (int j = i - 1; j >= 0 && notstop; j--) {
            //cout << nums.at(i) << "<" << nums.at(j) << endl;
            if (nums.at(i) <= nums.at(j)) {
                n_m.second = i;
                notstop = false;
            }
        }
    }

    return n_m;
}

int main()
{
    vector<int> nums = { 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19 };
    cout << sub_sort(nums).first << " ";
    cout << sub_sort(nums).second << endl;

    nums = { 1,2,3,4,5 };
    cout << sub_sort(nums).first << " ";
    cout << sub_sort(nums).second << endl;
}
```