My solution, flip 4 times per insertion
20 void _Flip(vector& a, int idx)
21 {
22 if (idx < 0 || idx >= a.size()) return;
23 int left = idx, right = a.size() - 1;
24 while (left < right) swap(a[left++], a[right--]);
25 }
26
27 void InsertByFlip(vector& a, int idx, int iPos)
28 {
29 // e.g. AB C DE --> ACB DE
30
31 _Flip(a, idx + 1); // AB C ED
32 _Flip(a, idx); // AB DE C
33
34 _Flip(a, iPos); // AC ED B
35 _Flip(a, iPos + 1); // ACB DE
36 }
37
38 int BiSearch(vector& a, int start, int end, int target)
39 {
40 while (start <= end) {
41 int mid = start + (end - start) / 2;
42 if (a[mid] < target) start = mid + 1;
43 else end = mid - 1;
44 }
45 return start;
46 }
47 void SortByFlip(vector& a)
48 {
49 for (int i = 1; i < a.size(); ++i) {
50 // find insert position (O(logN))
51 int iPos = BiSearch(a, 0, i - 1, a[i]);
52 if (iPos == i) continue;
53
54 // insert
55 InsertByFlip(a, i, iPos); // O(1)
56 }
57 }